Python及其内置堆

Question

目前，我正在尝试在Python中使用内置的heapq库来写一个优先队列。不过，我遇到了一个问题，就是不太明白Python是怎么处理优先级相同的情况的。我想要有一个特定的条件来决定在优先级相同的时候该怎么处理，而不是让heapq库看起来像是随机从队列中选一个。有没有人知道怎么重写这个优先级相同的处理方式，或者说从头开始自己构建一个优先队列会更简单呢？

Answer 1

heapq这个模块在处理队列里的项目时，会用到一些内置的比较方法（比如__le__等）。为了绕过这个限制，我们可以使用一种老办法，叫做“装饰/去装饰”，这在排序的时候也常用，尤其是在引入key=参数之前。

简单来说，当你把东西放进队列（enqueue）和从队列里取出东西（dequeue）时，不仅仅是放入你关心的内容（“有效载荷”），而是把这些内容“装饰”成一个元组，元组的开头是你希望heapq考虑的“关键字”。举个例子，如果你想根据x属性来优先排序，并且在x相同的情况下按插入时间来区分，那么你可以放入一个像(foo.x, time.time(), foo)这样的元组。当你从队列里取出东西时，就要“去装饰”，也就是取出元组中的最后一个元素。

所以，记得把你需要用来“打破平局”的“次要关键字”放在你放入队列的“装饰”元组里，顺序要在你想要用来打破平局的关键字之后。