Python 和内置堆

Question

目前，我正在尝试使用内置的 heapq 库在 Python 中编写优先级队列。但是，我一直试图弄清楚 Python 对打破平局的作用，我想要一个特定的条件，在这个条件下我可以指示打破平局会发生什么，而不是 heapq 库，它似乎几乎可以挑出一些东西队列随机。有人知道重写打破平局条件的方法吗？或者从头开始构建优先级队列会更容易吗？

Answer 1

heapq 使用队列项(__le__ 和 friends)的内在比较。绕过此限制的一般方法是称为“修饰/取消修饰”的好旧方法——这是我们在排序时使用的方法，在引入 key= 参数之前。

简单地说，您入队和出队，不仅仅是您关心的项目(“有效负载”)，而是“装饰”成以您需要的“键”开头的元组的项目 heapq 考虑。因此，例如，如果您希望通过 x 属性进行优先级排序，则将 (foo.x, time.time(), foo) 之类的元组入队是正常的通过插入队列的时间——当然，当你出队时你“取消修饰”，通过取出你得到的元组的 [-1]th 项目。

因此，只需将您需要考虑用于“打破平局”的“辅助键”放在您排队的“装饰”元组中，放在您想要以这种方式打破其“平局”的元组之后。