使用python打破优先级队列

Question

我正在使用堆队列来实现算法,当我向队列添加新节点时,它们按启发式函数排序:例如heappush(队列,(得分(节点),节点)),这太棒了,分开事实上,当我将下一个节点弹出队列时,我想要最近添加的节点,而不是第一个添加的节点,这就是heappop返回的节点.如何在不破坏队列的情况下将最新节点添加到队列中？

我想我可以在第一个元素开始迭代,而下一个元素具有相同的分数,继续.然后当我找到带有该分数的最终元素时,我选择它并将其从列表中删除.这显然不是非常有效,并且打破了优先级队列的时间复杂性？

我坚持这个,我无法想办法做到这一点.

谢谢.

编辑; 使用计数器,按照建议不起作用(也许我误解了)

>>> queue = []
>>> heappush(queue, (2, 0, 'a'))
>>> heappush(queue, (3, -1, 'b'))
>>> queue
[(2, 0, 'a'), (3, -1, 'b')]
>>> heappush(queue, (2, -2, 'c'))
>>> queue
[(2, -2, 'c'), (3, -1, 'b'), (2, 0, 'a')]

现在队列排序不正确,并且"b"比"a"更糟糕的选项放在它之前.

编辑2:

我勒个去？

>>> heappop(queue)
(2, -2, 'c')
>>> queue
[(2, 0, 'a'), (3, -1, 'b')]
>>> 

Answer 1

一种非常简单的方法是添加包含时间戳或计数器值的中间项.例如:

>>> heap = []
>>> counter = itertools.count()
>>> for i in range(10):
...     heapq.heappush(heap, (i, -next(counter), str(i) + ' oldest'))
...     heapq.heappush(heap, (i, -next(counter), str(i) + ' newest'))
... 
>>> heapq.heappop(heap)
(0, -1, '0 newest')
>>> heapq.heappop(heap)
(0, 0, '0 oldest')
>>> heapq.heappop(heap)
(1, -3, '1 newest')
>>> heapq.heappop(heap)
(1, -2, '1 oldest')

正如agf提到的,这是heapq文档使用的方法,只使用负指数.(那里的实现还包括一个很好的任务删除和优先级更改例程.)