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中提到，文档建议DIY实现heapq以减轻此问题。

为什么会发生这种情况？既然heapq是一个非常古老的库，为什么这样的冲突没有得到解决？是否存在性能/其他问题？为什么我们不能将像keep_old、keep_any这样的参数作为该库的功能提供？

- xxbidiao

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 的一个方面是操作应该是确定性的：决定胜负的方法不应该是随机的，并且由您根据具体情况决定如何处理。

- Brad Solomon

---

谢谢。我认为默认情况下没有提供3元组实现。仍然很惊讶你提供的实现没有作为默认行为打包（本质上是keep_new）。那个错误信息非常误导！ - xxbidiao

Answer 2

我的第一反应是堆需要有序；由于您向堆中添加了两个P0项目，并且当优先级相等时，堆会回退到对值进行排序，因此这些值必须有序。如果这是您想要的，我建议将map子类化为comparableMap（“k”，{“k”：0}），并在其中添加一个比较方法。

- Mr. Cat

---

这也是一个合理的方式，如果我有一个自定义类对象的话。 - xxbidiao