使用python在优先级队列中打破平局
提问于 2012-04-18 22:22:15
我正在使用堆队列来实现一个算法，当我将新节点添加到我的队列中时，它们通过一个启发式函数进行排序:例如heappush( queue，(score( node )，node))，这很棒，除了当我从队列中弹出下一个节点时，我想要最近添加的节点，而不是第一个添加的节点，这是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')]
>>> 
回答 1
Stack Overflow用户
回答已采纳
发布于 2012-04-18 22:30:10
一种非常简单的方法是添加一个包含时间戳或计数器值的中间项。举个例子：
>>> 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文档使用的方法，只使用负索引。(那里的实现还包括一个很好的任务删除和优先级更改例程。)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/10218953
复制
![[Go]解决goland terminal 环境变量不更新](https://ask.qcloudimg.com/http-save/yehe-2504969/9vzn4pe6dd.png)
腾讯云开发者
