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.
Add a comment
|
2 Answers
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.
answered Feb 27, 2013 at 22:53
Martijn Pieters
1.1m326 gold badges4.2k silver badges3.4k bronze badges
2 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.
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')
