如果项目不可比较，heapq 无法处理具有相同优先级的元组

Question

>>> from heapq import heappush
>>> heap = []
>>> heappush(heap,(0,{"k":0}))
>>> heappush(heap,(0,{"k":1}))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'dict' and 'dict'

python2和 python3的官方 heapq 文档中提到了这一点，该文档建议使用 DIY 实现来缓解此问题。heapq

为什么会发生这种情况？heapq鉴于这是一个非常旧的库，这种冲突没有得到解决的根本原因是什么？是否有性能/其他问题？为什么我们不能只提供参数keep_old, keep_any作为该库的功能？

Answer 1

来自优先级队列实现说明的heapq文档部分：

前两个挑战的解决方案是将条目存储为三元素列表，包括优先级、条目计数和任务。条目计数充当决胜局，以便具有相同优先级的两个任务按照添加顺序返回。

对此的简单解释是：

from heapq import heappush
ecount = 0
heap = []

for priority, task in (
    (0, {"k":0}),
    (0, {"k":0}),
):
    heappush(heap, (priority, ecount, task))
    ecount += 1

结果：

>>> heap
[(0, 0, {'k': 0}), (0, 1, {'k': 0})]

（您也可以使用 执行此操作enumerate()。）

注入一些观点：

为什么会发生这种情况？鉴于 heapq 是一个非常旧的库，这种冲突没有得到解决的根本原因是什么？

不太确定，但事实是你无法从逻辑上比较两个dict小于/大于。

独立于heapq，比较(0,{"k":0}) > (0,{"k":1})将（理所当然地）提高TypeError。 强调的heapq是操作应该是确定性的：抢七局不应该是随机的，并且由您根据具体情况确定如何处理。