不考虑 PriorityQueue 中元素优先级的更新

Question

from queue import PriorityQueue

pq = PriorityQueue()
x = [20,0]
y = [20,0]
pq.put(x)
pq.put(y)
y[1] = -1
print(x,y) 
while not pq.empty():
    print(pq.get())

以上程序的输出为：

[20,0]
[20,-1]

输出应按升序排列：

[20,-1]
[20,0]

Answer 1

通过在将其放入队列后对其进行变异，您可以绕过优先级队列的逻辑。不会通知您所做的更新。

如果你真的必须修改一个已经在队列中的元素的优先级，那么首先使它无效，然后添加一个新元素作为替换：

from queue import PriorityQueue

inf = float("inf")
pq = PriorityQueue()
x = [20,0]
y = [20,0]
pq.put(x)
pq.put(y)

# create a copy that has the desired modification
newy = [y[0], -1]
pq.put(newy)
# invalidate the element that was already in the queue
y[0] = -inf 
y[1] = -inf

while not pq.empty():
    val = pq.get()
    # ignore invalidated entries
    if val[0] != -inf:
        print(val)

另一种方法是使用 heapq 而不是 queue.PriorityQueue，改变元素然后调用 heapify 来恢复堆属性.

from heapq import heapify, heappush, heappop

heap = []
x = [20,0]
y = [20,0]
heappush(heap, x)
heappush(heap, y)

# mutate...
y[1] = -1
# ...and heapify
heapify(heap)

while heap:
    print(heappop(heap))

这看起来更简单，但请注意 heapify 具有线性时间复杂度：它访问堆的所有元素。

不考虑 PriorityQueue 中元素优先级的更新

Update of element's priority in PriorityQueue is not taken into account

python

indexing

priority-queue

pass-by-reference