目前,我正在尝试使用内置的 heapq 库在 Python 中编写优先级队列。但是,我一直试图弄清楚 Python 对打破平局的作用,我想要一个特定的条件,在这个条件下我可以指示打破平局会发生什么,而不是 heapq 库,它似乎几乎可以挑出一些东西队列随机。有人知道重写打破平局条件的方法吗?或者从头开始构建优先级队列会更容易吗?
最佳答案
heapq
使用队列项(__le__
和 friends)的内在比较。绕过此限制的一般方法是称为“修饰/取消修饰”的好旧方法——这是我们在排序时使用的方法,在引入 key=
参数之前。
简单地说,您入队和出队,不仅仅是您关心的项目(“有效负载”),而是“装饰”成以您需要的“键”开头的元组的项目 heapq
考虑。因此,例如,如果您希望通过 x
属性进行优先级排序,则将 (foo.x, time.time(), foo)
之类的元组入队是正常的通过插入队列的时间——当然,当你出队时你“取消修饰”,通过取出你得到的元组的 [-1]
th 项目。
因此,只需将您需要考虑用于“打破平局”的“辅助键”放在您排队的“装饰”元组中,放在您想要以这种方式打破其“平局”的元组之后。
关于Python 和内置堆,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1422969/