如何在Python中删除堆中的特定元素而不丢失堆属性？

Question

我正在尝试实现一种算法来解决天际线问题，该问题涉及从最大堆中间删除特定元素。我目前的做法是

maxheap.remove(index)

但我必须跟进

heapify(maxheap)

否则订单就会被取消。我知道在 Java 中你可以使用像

treemap

这样的东西来做到这一点。无论如何，在 python 中是否有比调用两个单独的方法（每个方法都需要 O(n) 时间）更有效的方法？

Answer 1

从堆中删除任意项目是一个 O(log n) 操作，前提是您知道该项目在堆中的位置。算法是：

Move the last item in the heap to the position that contains the item to remove.
Decrement heap count.
If the item is smaller than its parent
    bubble it up the heap
else
    sift it down the heap

首要问题是查找该项目在堆中的位置。正如您所指出的，除非您维护更多信息，否则这样做是一个 O(n) 操作。

对此的一个有效解决方案是创建一个包含项目键的字典，而值是该项目在堆中的索引。但是，您必须维护字典：

1. 当你向堆中插入一个项目时，添加一个字典条目
2. 当您从堆中删除项目时，也会删除字典条目
3. 每当您更改堆中某个项目的位置时，请更新该项目在字典中的值。

有了该字典，您就可以 O(1) 访问堆中某个项目的位置，并且可以在 O(log n) 中删除它。

Answer 2

我会让每个元素都是一个带有是否忽略它的标志的数据结构。当您弹出时，如果它是一个被标记的元素，您将再次弹出。这非常简单、明显，并且不需要了解堆内部如何工作。例如，您不需要知道该元素实际位于堆中的位置即可对其进行标记。

这种方法的缺点是标记的元素会随着时间的推移而积累。有时您可以将它们过滤掉然后进行堆化。

如果这个解决方案不足以满足您的需求，您应该在 Python 中寻找某种 btree 实现。这将像您在 Java 中习惯的树形图一样。

Answer 3

是的，有一种更有效的方法 - 如果你有它的索引或指针（取决于实现方法）。

将需要删除的索引/指针上的数字替换为其最大的数字 子节点并递归地重复该过程（用最大的子节点替换子节点等），直到到达没有子节点的节点，您可以轻松删除该节点。

该算法的复杂度为O(log n)。

http://algorithms.tutorialhorizon.com/binary-min-max-heap/

Answer 4

这是一个老问题，但是没有代码感觉不完整。我已经实现了一个 happypath 堆，能够根据其值删除元素。

希望这对以后查看这里的人有用。

from collections import defaultdict


class HeapSet:
    def __init__(self):
        self.heap = []
        self.positions = defaultdict(set)

    def _swap(self, i: int, j: int):
        obj = self.heap[i]
        swap_with_obj = self.heap[j]
        if obj == swap_with_obj:
            return

        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

        self.positions[obj].add(j)
        self.positions[obj].remove(i)

        self.positions[swap_with_obj].add(i)
        self.positions[swap_with_obj].remove(j)

    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.positions[obj].add(self.size() - 1)
        self._swim(self.size() - 1)

    def remove(self, obj):
        pos = next(iter(self.positions[obj]))
        self._swap(pos, self.size() - 1)
        self.positions[obj].remove(self.size() - 1)
        self.heap.pop()

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

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

        return self.heap[0]

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