從二進制最大堆中刪除第二小元素

此問題與this類似。區別在於我有一個二進制最大堆而不是最小堆。這使問題完全不同。從二進制最大堆中刪除第二小元素

我的想法：

1）我經歷的所有節點，以找到第二個最小的元素，這將需要O（n）的

2）當我找到第二個最小的元素，我泡那元素，通過交換它的父元素直到它到達根，這將花費O（logn）

3）我從根中刪除該元素，並採取最右邊的元素，並將其存儲在根位置（常規堆刪除操作），這將花費O（logn）

總數爲O（n）+ O（logn）+ O（logn），即O（n）。

編輯：新增二進制

難道還有比這更好的解決方案呢？

來源

2012-05-09 Roronoa Zoro

爲什麼不使用分鐘堆？無論如何，任何有效的解決方案都會間接地創建最小堆。 – ElKamina

@ElKamina;這是一個問題（不是家庭作業），我有興趣知道答案。 –

我假設你說的「堆」是指[二進制堆]（http://en.wikipedia.org/wiki/Binary_heap） - 是否正確？ – amit

第二小的元素是一片葉子或葉子的父親，葉子是它的唯一孩子。

如何刪除第二個最小的元素：

搜尋通過樹葉以及可能只有一個孩子父親搜索。 O（n）
如果第二小元素是節點的父節點，則該節點必須是最小元素並且應該是最右邊的葉子。將其第二小的替換爲其小孩，並且結束。 O（1）
如果第二個元素是一個葉子，用最右邊的葉子取代最深層次並冒泡。 O（log（n））

因此，它仍然是O（n）O（n）+ O（log（n）），但比較次數較少。

來源

2012-05-09 15:32:49 hhsaffar

當談到大O符號 - 不，它不能做得更好。在最大堆中查找任意元素是O(n)。

但是，您可以將需要遍歷的最大節點數減少到1/2 * n，實質上是算法的速度的兩倍。 [仍然O(n)域]，因爲最大堆中的第二小元素至多有一個兒子，因此只能遍歷樹葉（其中n/2個），而最多隻有一個元素只有一個子元素。（請記住，二進制堆是一個表示完整樹的數組，因此至多有一個元素只有一個子元素）。

人們也可以加強一下刪除步驟，但我懷疑它會有任何顯着的影響），所以我不打算付出努力。

來源

2012-05-09 15:35:02 amit

爲什麼不保留一個有2個元素的小陣列來保留最小2個元素的副本？

然後，所有的操作都只是改變O（1）的步驟，你可以在固定的時間提供答案。

來源

2012-07-10 12:33:47 Churrupipi

從二進制最大堆中刪除第二小元素

回答

相關問題