Python:从堆中删除元素 [英] Python: delete element from heap

问题描述

Python具有heapq模块，该模块实现堆数据结构，并且支持一些基本操作(push，pop).

Python has heapq module which implements heap data structure and it supports some basic operations (push, pop).

如何从O(log n)的堆中删除第i个元素? heapq甚至有可能还是我必须使用另一个模块?

How to remove i-th element from the heap in O(log n)? Is it even possible with heapq or do I have to use another module?

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

Note, there is an example at the bottom of the documentation: http://docs.python.org/library/heapq.html which suggest a possible approach - this is not what I want. I want the element to remove, not to merely mark as removed.

推荐答案

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

You can remove the i-th element from a heap quite easily:

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

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

Just replace the element you want to remove with the last element and remove the last element then re-heapify the heap. This is O(n), if you want you can do the same thing in O(log(n)) but you'll need to call a couple of the internal heapify functions, or better as larsmans pointed out just copy the source of _siftup/_siftdown out of heapq.py into your own code:

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

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

Note that in each case you can't just do h[i] = h.pop() as that would fail if i references the last element. If you special case removing the last element then you could combine the overwrite and pop.

请注意，根据堆的典型大小，您可能会发现，仅调用heapify虽然理论上效率较低，但比重新使用_siftup/_siftdown更快:稍作内省就会发现heapify可能是用C实现的，但是内部函数的C实现并未公开.如果性能对您很重要，则可以考虑对典型数据进行一些时序测试，以了解哪种方法最好.除非您的堆真的很大，否则大O可能不是最重要的因素.

Note that depending on the typical size of your heap you might find that just calling heapify while theoretically less efficient could be faster than re-using _siftup/_siftdown: a little bit of introspection will reveal that heapify is probably implemented in C but the C implementation of the internal functions aren't exposed. If performance matter to you then consider doing some timing tests on typical data to see which is best. Unless you have really massive heaps big-O may not be the most important factor.

编辑:有人尝试编辑此答案，以删除对_siftdown的呼叫，并带有以下注释:

someone tried to edit this answer to remove the call to _siftdown with a comment that:

_siftdown不需要.保证新h [i]是旧h [i]的最小子项​​，但仍大于旧h [i]的父项 (新h [i]的父母). _siftdown将为空.我必须编辑 没有足够的代表来添加评论.

_siftdown is not needed. New h[i] is guaranteed to be the smallest of the old h[i]'s children, which is still larger than old h[i]'s parent (new h[i]'s parent). _siftdown will be a no-op. I have to edit since I don't have enough rep to add a comment yet.

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

What they've missed in this comment is that h[-1] might not be a child of h[i] at all. The new value inserted at h[i] could come from a completely different branch of the heap so it might need to be sifted in either direction.

还询问为什么不只使用sort()来还原堆的评论:调用_siftup和_siftdown都是O(log n)操作，调用heapify是O(n).调用sort()是O(n log n)操作.很有可能调用排序会足够快，但是对于大堆来说，这是不必要的开销.

Also to the comment asking why not just use sort() to restore the heap: calling _siftup and _siftdown are both O(log n) operations, calling heapify is O(n). Calling sort() is an O(n log n) operation. It is quite possible that calling sort will be fast enough but for large heaps it is an unnecessary overhead.

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

Edited to avoid the issue pointed out by @Seth Bruder. When i references the end element the _siftup() call would fail, but in that case popping an element off the end of the heap doesn't break the heap invariant.

这篇关于Python:从堆中删除元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！