Python：从堆中删除元素

Question

Python具有heapq实现堆数据结构的模块，并且它支持一些基本操作（推送，弹出）。

如何从O（log n）中的堆中删除第i个元素？甚至可以使用heapq还是必须使用另一个模块？

请注意，文档底部有一个示例：http :
//docs.python.org/library/heapq.html
，它建议了一种可能的方法-这不是我想要的。我希望删除元素，而不仅仅是标记为已删除。

Answer 1

您可以很容易地从堆中删除第i个元素：

h[i] = h[-1]
h.pop()
heapq.heapify(h)

只需将要删除的元素替换为最后一个元素，然后删除最后一个元素，然后重新堆化堆即可。这是O（n），如果需要，您可以在O（log（n））中做同样的事情，但是您需要调用几个内部的heapify函数，或者更好的是，如larsmans指出的那样，只需复制将_siftup
/ _siftdown从heapq.py转换为您自己的代码：

h[i] = h[-1]
h.pop()
if i < len(h):
    heapq._siftup(h, i)
    heapq._siftdown(h, 0, i)

请注意，在每种情况下您都不能这样做h[i] = h.pop()，因为如果i引用最后一个元素，该操作将失败。如果特殊情况下删除最后一个元素，则可以结合覆盖和弹出。

请注意，根据堆的典型大小，您可能会发现，仅heapify在理论上效率较低的情况下进行调用可能比重用_siftup/快一些_siftdown：进行一些自省会发现这heapify可能是用C实现的，但是内部函数的C实现没有暴露。如果性能对您很重要，则可以考虑对典型数据进行一些时序测试，以了解哪种方法最好。除非您的堆真的很大，否则大O可能不是最重要的因素。

编辑： 有人试图编辑此答案，以删除_siftdown带有以下内容的通话：

不需要_siftdown。保证新h [i]是旧h [i]的最小子项​​，但仍大于旧h [i]的父（新h
[i]的父）。_siftdown将为空。由于我没有足够的代表来添加评论，因此我必须进行编辑。

他们在此评论中错过的h[-1]可能根本不是孩子h[i]。插入的新值h[i]可能来自堆的完全不同的分支，因此可能需要沿任一方向进行筛选。

同样在询问为什么不仅仅用于sort()还原堆的评论中：调用_siftup和_siftdown都是O（log
n）操作，调用heapify就是O（n）。调用sort()是一个O（n log n）操作。调用排序很有可能足够快，但是对于大堆来说，这是不必要的开销。

编辑 以避免@Seth
Bruder指出的问题。当i引用end元素时，_siftup()调用将失败，但是在那种情况下，将元素从堆的末端弹出不会破坏堆的不变性。