9

我正在使用堆队列来实现算法，当我将新节点添加到队列中时，它们会按启发式函数排序：例如 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')]

现在队列的排序不正确，并且比 'a' 更糟糕的选项 'b' 被放置在它之前。

编辑2：

我勒个去？

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

1 回答 1

12

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

>>> 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文档使用的方法，仅使用负索引。（那里的实现还包括一个不错的任务删除和优先级更改例程。）

于 2012-04-18T22:30:09.683 回答