Priority queue with higher priority first in Python

Question

I need a priority queue that gets the item with the highest priority value first. I'm currently using the PriorityQueue Class from the Queue library. However, this function only returns the items with the lowest value first. I tried some ugly solutions like (sys.maxint - priority) as the priority, but was just wondering if a more elegant solution exists.

Solution 1

Use a negative priority instead, no need to subtract from sys.maxint.

queue.put((-priority, item))

An item with priority -10 will be returned before items with priority -5, for example.

Solution 2

You can extend the Priority Queue to keep the logic unchanged:

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())

Output:

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

Comments

[onesiumus]

While this works, it honestly bothers me because that implies all other associated logic has be reversed in your head.

[Martijn Pieters]

@blueman: then subclass the queue class and override the methods to invert the priority for you.