Python和内置堆

Question

目前，我想写使用内置的heapq库Python中的优先级队列。然而，我试图弄清楚Python在打破平局方面所做的工作，我想要有一个特定的条件，在那里我可以决定打破平局会发生什么，而不是heapq库，似乎几乎可以选择某些东西随机排队。是否有人知道重写破解条件的方法，还是从头开始构建优先队列更容易？

Answer 1

heapq使用队列项目（__le__和朋友）的内在比较。要解决此限制的一般方法是被称为“装饰/去除装饰”好老办法 - 这就是我们使用排序做，引入了key=参数之前就有。

简而言之，您入队和出队，不仅仅是您关心的项目（“有效载荷”），而是将项目“装饰”为需要考虑的“钥匙”开头的元组。因此，例如，如果您想通过x属性优先化排列元组，那么这将是正常的，因为按照插入队列的时间将关系中断 - 当然，当您将队列解除排队时，通过取[-1]通过排队获得的元组的第一项。

所以，只需将“次要钥匙”放入您要排队的“装饰”元组中的“tie-breaking”中即可。