从 python 中的堆中删除任意项目

Question

是否有二进制堆实现，我可以在 log n 次中弹出除根以外的其他元素？

我使用 heapq - 但 heap.index( wKeys ) 在

heap.pop( heap.index( wKeys ) )

非常慢。我需要一个二进制堆来解决我的问题——我有时会在其中使用

heapq.heappop(heap)

但还需要从堆顶弹出其他元素。所以像 heapq imlementation 这样的二进制堆应该这样做，但我还没有找到二进制搜索方法。我也查看了 treap (http://stromberg.dnsalias.org/~strombrg/treap/)，但在这里也找不到这样的方法。

Answer 1

我通过向 heappop() 和 heappush() 添加一个参数来修改 heapq 的实现 - 即 heapIndex。这需要 {item: index} 的字典并在 heapIndex 弹出或推入 heap 时更新 heapIndex。

我还添加了一个新方法 heappop_arbitrary() 删除任意元素并更新 heapIndex

代码可在此处获得：https://github.com/emoen/heapq_with_index

我已将方法 heappop(),heappush() 重命名为 heappop2(), heappush2() 以避免与原始方法混淆。

我还没有为 heapq 中可用的任何其他函数实现这个。

编辑：如果您可以使用该存储库，请加注星号:)

Answer 2

class RemoveHeap:
    def __init__(self):
        self.h = []
        self.track = collections.defaultdict(collections.deque)
        self.counter = itertools.count()

    def insert_item(self, val):
        count = next(self.counter)
        item = [val, count, 'active']
        self.track[val].append(item)
        heapq.heappush(self.h, item)

    def delete_item(self, val):
        if val in self.track:
            items = self.track[val]
            for item in items:
                if item[2] == 'active':
                    item[2] = 'deleted'
                    break

    def pop_item(self):
        while len(self.h) > 0:
            item = heapq.heappop(self.h)
            item_track = self.track[item[0]]
            item_track.popleft()
            if len(item_track) == 0:
                del self.track[item[0]]
            else:
                self.track[item[0]] = item_track
            if item[2] == 'active':
                return item[0]

    def peek_item(self):
        item = self.h[0]
        if item[2] == 'deleted':
            x = self.pop_item()
            self.insert_item(x)
            return x
        return item[0]

从 python 中的堆中删除任意项目

delete arbitrary item from heap in python

python

heap

binary-heap

data-structures