从优先队列中移除项目

Question

在Python中，heapq模块提供了一种优先队列。

这个模块有一些方法可以用来添加和移除队列里的项目。

如果你想从队列中移除一个你之前添加的项目，但这个项目的优先级不是最低的，该怎么做呢？

如果你有其他方法可以用不同的集合来实现这个功能，也欢迎分享哦。

Answer 1

这个 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)

Answer 2

如果你知道想要删除的项目的位置，可以这样做：

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

第一步现在的时间复杂度是O(1)，也就是说这一步非常快。第二步可以通过使用一些不公开的数据，把时间复杂度降低到O(log(N))。当然，如果你事先没有找到k，还是需要O(N)的时间来找到它。

Answer 3

heapq模块是用标准的Python列表作为基础数据结构的，所以你可以在这之后直接使用标准的list方法remove()和heapify()。不过要注意，这个过程需要线性时间，也就是说时间复杂度是O(n)。

# 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)。