Python中的优先队列，优先处理高优先级

Question

我需要一个优先队列，它能先取出优先级最高的项目。目前我在用Python的Queue库里的PriorityQueue类。不过这个功能只会先返回优先级最低的项目。我试过一些不太好看的解决办法，比如用(sys.maxint - priority)来表示优先级，但我在想有没有更优雅的解决方案。

Answer 1

你可以扩展优先队列，这样逻辑就不会改变：

from Queue import PriorityQueue

class DualPriorityQueue(PriorityQueue):
    def __init__(self, maxPQ=False):
        PriorityQueue.__init__(self)
        self.reverse = -1 if maxPQ else 1

    def put(self, priority, data):
        PriorityQueue.put(self, (self.reverse * priority, data))

    def get(self, *args, **kwargs):
        priority, data = PriorityQueue.get(self, *args, **kwargs)
        return self.reverse * priority, data


minQ = DualPriorityQueue()
maxQ = DualPriorityQueue(maxPQ=True)

minQ.put(10, 'A')
minQ.put(100, 'A')


maxQ.put(10, 'A')
maxQ.put(100,'A')

print "Min DQ: {}".format(minQ.get())
print "Max DQ: {}".format(maxQ.get())

输出结果：

Min DQ: (10, 'A')
Max DQ: (100, 'A')

Answer 2

可以使用负数优先级，不需要从 sys.maxint 中减去什么。

queue.put((-priority, item))

比如说，优先级为 -10 的项目会比优先级为 -5 的项目先被返回。