從堆中刪除第i個節點

我知道從堆中刪除節點是發生在根上的O(log n)。而且我也知道在堆樹問題之一中刪除一個堆中的任意節點並且是O(n)。從堆中刪除第i個節點

是否有減少從maxheap刪除Ith的節點O(log n)其中我是從1至N的運行時間的任何算法？

2011-02-24 Novice

從堆刪除的任意的節點的昂貴的部分不處於刪除，但在發現刪除的節點。實際上刪除節點是O（log n）。但首先，您必須對底層數據存儲進行順序掃描才能找到節點。這是O（n）部分。

加快這唯一的辦法是保持第二數據結構就像一本字典或哈希映射或類似，能夠迅速告訴你，該項目是在後備存儲。然後，您在字典中進行O（1）查找，從字典中刪除O（1），並從堆中刪除O（log n）。

2011-02-24 16:01:12

謝謝您Jim.do意味着如果指定_I_，運行時間爲O（log n）的λ最大堆陣列是[1000，800，第7，400,600，5個，4，100，200，300， 500]，我想從中刪除7，但是我不能在O（log n）中刪除它... – Novice 2011-02-24 16:18:45

如果你想從列表中刪除'7'，那麼運行時間是O（n），因爲第一個您必須搜索列表才能在數組中找到'7'的索引（2）。但是，如果您已經知道要刪除的項目位於數組的索引（2）處，那麼將其刪除爲O（log n）。 – 2011-02-24 16:23:41

回答