Python:从堆中删除元素

Question

Python具有heapq实现堆数据结构的模块,它支持一些基本操作(push,pop).

如何从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指出只是复制源代码将heapq.py中的_siftup/_siftdown转换为您自己的代码:

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被保证是最小的旧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)操作.调用sort很可能足够快,但对于大堆来说,这是一个不必要的开销.

编辑以避免@Seth Bruder指出的问题.当i引用end元素时,_siftup()调用将失败,但在这种情况下,从堆的末尾弹出一个元素不会破坏堆不变量.

Answer 2

(a)考虑为什么你不想懒惰删除.在很多情况下,这是正确的解决方案.

(b)堆是一个列表.您可以按索引删除元素,就像任何其他列表一样,但是您需要重新堆积它,因为它将不再满足堆不变量.