Priority Queue

Priority Queue

An implementation of priority queue is captured here:

Ref: https://www.safaribooksonline.com/library/view/python-cookbook-3rd/9781449357337/ch01s05.html

Problem:

You want to implement a queue that sorts items by a given priority and always returns the item with the highest priority on each pop operation.

'''
The following class uses the heapq module to implement a simple priority queue
'''
import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

An example on how to use it:

>>> class Item:
...     def __init__(self, name):
...         self.name = name
...     def __repr__(self):
...         return 'Item({!r})'.format(self.name)
...
>>> q = PriorityQueue()
>>> q.push(Item('foo'), 1)
>>> q.push(Item('bar'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('grok'), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')
>>>

Discussion

The core of this recipe concerns the use of theheapqmodule. The functionsheapq.heappush()andheapq.heappop()insert and remove items from a list_queuein a way such that the first item in the list has the smallest priority (as discussed inRecipe 1.4). Theheappop()method always returns the “smallest” item, so that is the key to making the queue pop the correct items. Moreover, since the push and pop operations have O(log N) complexity where N is the number of items in the heap, they are fairly efficient even for fairly large values of N.

In this recipe, the queue consists of tuples of the form(-priority, index, item). _Thepriorityvalue is negated to get the queue to sort items from highest priority to lowest priority. _This is opposite of the normal heap ordering, which sorts from lowest to highest value.

_The role of theindexvariable is to properly order items with the same priority level. By keeping a constantly increasing index, the items will be sorted according to the order in which they were inserted. _However, the index also serves an important role in making the comparison operations work for items that have the same priority level.

If you make

(priority, item)

tuples, they can be compared as long as the priorities are different. However, if two tuples with equal priorities are compared, the comparison fails as before. For example:

>>> a = (1, Item('foo'))
>>> b = (5, Item('bar'))
>>> a < b
True
>>> c = (1, Item('grok'))
>>> a < c
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>

By introducing the extra index and making

(priority, index, item)

tuples, you avoid this problem entirely since no two tuples will ever have the same value for

index

(and Python never bothers to compare the remaining tuple values once the result of comparison can be determined):

>>> a = (1, 0, Item('foo'))
>>> b = (5, 1, Item('bar'))
>>> c = (1, 2, Item('grok'))
>>> a < b
True
>>> a < c
True
>>>