python - python中具有重复键的优先级队列

Question

我有以下场景 -

In [2]: from heapq import heappush, heappop

In [3]: pq =[]

In [4]: heappush(pq, (2, "I hate sth"))

In [5]: heappush(pq, (2, "I love sth"))

In [6]: heappush(pq, (2, "I gate sth"))

In [7]: heappop(pq)
Out[7]: (2, 'I gate sth')

这里我希望堆返回(2，“我讨厌某事”)我的意思是如果有任何重复项，那么它应该返回首先插入的最小项目。我知道这里的项目是元组，所以第三个显然很小。

但是有什么方法可以单独存储优先级和字符串，并且如果存在平局，则按插入顺序返回项目。

谢谢

Answer 1

这个属性称为稳定性:如果两个对象被推送到堆上并且具有相同的优先级，那么它们会以相同的顺序弹出。
python 标准库文档现在回答了您的问题: https://docs.python.org/3/library/heapq.html#priority-queue-implementation-notes
它提供了两种解决方案，一种是使用 3 元组(key、insertion_count、value)，另一种是使用新的项类型 PrioritizedItem，它会忽略 ( key, value) 对，并且仅根据键进行排序。该脚本显示了您的示例和相关解决方案:

from heapq import heappush, heappop
from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

pq = []
heappush(pq, (2, "I hate sth"))
heappush(pq, (2, "I love sth"))
heappush(pq, (2, "I gate sth"))
print("PQ items as tuples")
print("popped item:")
print(heappop(pq))

print("=====")
pq_insertion_order = []
heappush(pq_insertion_order, PrioritizedItem(2,"I hate sth"))
heappush(pq_insertion_order, PrioritizedItem(2,"I late sth"))
heappush(pq_insertion_order, PrioritizedItem(2,"I gate sth"))
print("PQ items as PrioritizedItem")
print("popped item:")
print(heappop(pq_insertion_order))

运行这个脚本我们得到:

PQ items as tuples
popped item:
(2, 'I gate sth')
=====
PQ items as PrioritizedItem
popped item:
PrioritizedItem(priority=2, item='I hate sth')

由于堆是稳定的，因此使用 PrioritizedItem 问题就解决了。
同样的方法也可以用于queue.PriorityQueue 类。 PriorityQueue 弹出元素与 sorted(list(entries))[0] 相同，并且由于 sorted() 是稳定的，因此使用此使用 PrioritizedItem 的方法也很稳定。