在python中从堆中删除任意项

Question

是否有一个二进制堆实现，我可以在logn time中弹出除根以外的其他元素？在

我在中使用heapq-butheap.index( wKeys )

heap.pop( heap.index( wKeys ) )

很慢。我需要一个二进制堆来解决我的问题-我有时会用到

^{pr2}$

但也需要从堆的顶部弹出其他元素。所以像heapq-imement这样的二进制堆应该可以做到这一点，但我还没有找到二进制搜索方法。我还研究了treap（http://stromberg.dnsalias.org/~strombrg/treap/），在这里也找不到这样的方法。在

Answer 1

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

我还添加了一个新的方法heappop_arbitrary()，它删除任意元素并更新{}

代码在这里可用：https://github.com/emoen/heapq_with_index

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

我还没有为heapq中可用的任何其他功能实现这个功能。在