从堆中删除第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

回答