从优先级队列中删除项目

Question

在Python中,heapq模块提供优先级队列.

它有插入和弹出项目的方法.

如何从队列中删除已插入但不是最低优先级的项目？

(也欢迎使用替代其他收藏品的替代食谱)

Answer 1

该heapq模块采用标准的Python列表作为底层的数据结构,所以你可以使用标准的list方法remove()和heapify()后再次这一点.请注意,这将需要线性时间.

# Create example data and heapify
a = range(10)
a.reverse()
heapq.heapify(a)
print a

# remove an element and heapify again
a.remove(5)
heapq.heapify(a)
print a

您可以通过使用未记录的函数再次提高堆积的性能heapify._siftup(),但整个过程仍然是O(n),因为list.remove()是O(n).

Answer 2

如果您知道要删除的项目的位置,则可以执行以下操作:

a[k] = a.pop()
heapq.heapify(a)

第一步现在是O(1)时间,第二步可以通过使用未记录的数据制作O(log(N)).当然,如果你还没有找到k,它仍然是O(N).

Answer 3

这个 log(N) 函数对我有用：

def heapq_remove(heap, index):
    """Remove item from heap"""

    # Move slot to be removed to top of heap
    while index > 0:
        up = (index + 1) / 2 - 1
        heap[index] = heap[up]
        index = up

    # Remove top of heap and restore heap property
    heapq.heappop(heap)