Python：从堆中删除元素

Question

Python：从堆中删除元素

pythonheap

69

Python有heapq模块，实现了堆数据结构，并支持一些基本操作（push、pop）。

如何在O(log n)时间内从堆中删除第i个元素？使用heapq是否可能实现，还是我需要使用另一个模块？

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

- Ecir Hana

3个回答

23

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

(b) 堆是一个列表。您可以像任何其他列表一样按索引删除元素，但然后需要重新堆化它，因为它不再满足堆不变量。

- Marcin

1

你能为(b)添加一些参考资料吗？ - Zenon

1

@Zenon b 的哪一部分？您可以在解释器中查看对象的类型，或阅读 OP 链接的文档；至于需要重新堆化，这是因为这样的操作会导致违反堆不变量的列表（也在该文档中给出）。 - Marcin

(a) - 惰性删除是完全有效的，我只是想更好地理解堆。 (b) 我对至少O(log n)感兴趣，堆化是O(n)。 - Ecir Hana

2

惰性删除是绕过堆的O(N)删除成本的天才方法。 - anthonybell

2

如果有人想知道什么是“懒惰删除”，可以在下面找到相关文章，但基本上在这种情况下，您会在键值存储中将元素标记为“已删除”，但实际上不会从堆中删除它，因为那需要O(n)时间。然后，当您使用堆时，可以检查该键值存储是否将您正在查看的节点标记为已删除。它用于哈希表，但也可以在这里使用 https://en.wikipedia.org/wiki/Lazy_deletion - athammer

0

实现了一个支持按索引删除的堆的面向对象示例。基本上与被接受的答案中的示例相同，只是一个快乐路径的类示例。

希望这对以后查看这里的人有所帮助。

class RemoveByIndexHeap:
    def __init__(self):
        self.heap = []

    def _swap(self, i: int, j: int):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def _sink(self, i: int):
        while i < self.size():
            swap_with = i
            if i * 2 + 1 < self.size() and self.heap[swap_with] > self.heap[i * 2 + 1]:
                swap_with = i * 2 + 1
            if i * 2 + 2 < self.size() and self.heap[swap_with] > self.heap[i * 2 + 2]:
                swap_with = i * 2 + 2
            if swap_with == i:
                break
            else:
                self._swap(i, swap_with)
                i = swap_with

    def _swim(self, i: int):
        while i > 0:
            swap_with = i
            if (i - 1) // 2 >= 0 and self.heap[swap_with] < self.heap[(i - 1) // 2]:
                swap_with = (i - 1) // 2
            if swap_with == i:
                break
            else:
                self._swap(i, swap_with)
                i = swap_with

    def add(self, obj):
        self.heap.append(obj)
        self._swim(self.size() - 1)

    def remove(self, index: int):
        self._swap(index, self.size() - 1)
        self.heap.pop()

        if index != self.size():
            self._sink(index)
            self._swim(index)

    def get_top(self):
        if not self.heap:
            return None

        return self.heap[0]

    def size(self):
        return len(self.heap)

- Sibay

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Duncan · Accepted Answer

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

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

只需将要删除的元素替换为最后一个元素，然后删除最后一个元素并重新对堆进行堆化。这个过程的时间复杂度为O(n)，如果你想使用O(log(n))的时间复杂度，需要调用一些内部的堆化函数，或者更好的做法是像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[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) 操作。调用 sort 足够快是很有可能的，但对于大的堆来说，这是一种不必要的开销。

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