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

Question

我正在尝试实现一个算法来解决天际线问题，该问题涉及从最大堆的中间删除特定元素。目前我使用的方法是maxheap.remove(index)，但我必须跟进heapify(maxheap)，否则次序会被扰乱。我知道在java中可以使用像treemap这样的东西。在Python中有没有更高效的方法来调用两个单独的方法，每个方法都需要O(n)的时间?

- YSA

---

你指的是哪种堆实现？如果它包含 remove（表示显式访问堆元素）操作符，那么它也可能包含 change priority 操作符。 - MBo

@MBo 在Python中，显而易见的实现是使用标准库中的heapq。 - btilly

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)的时间将其移除。

- Jim Mischel

Answer 2

我会让每个元素都成为一个数据结构，并带有一个标志来确定是否忽略它。当你执行heappop操作时，如果弹出的是被标记的元素，那么你只需要再次弹出即可。这种方法非常简单、明显，而且不需要了解堆内部的工作原理。例如，你不需要知道元素实际上在堆中的位置才能标记它。

这种方法的缺点是被标记的元素会随着时间的推移而越来越多。偶尔你可以将它们过滤掉然后进行堆排序。

如果这种方法不能满足你的需求，你应该寻找Python中的某种btree实现。这将像Java中你所熟悉的treemap一样运行。

- btilly

Answer 3

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

用其最大子代替您需要删除的索引/指针上的数字，并递归地重复此过程（用其最大子代替子代等），直到到达没有子代的节点，然后轻松删除它。

此算法的复杂度为O（log n）。

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

- Dorijan Cirkveni

Answer 4

这是一个老问题，但是没有代码的话感觉不完整。我已经实现了一个具有删除元素功能的快乐路径堆。

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

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)

- Sibay