Python priority queue example

1. What is a Priority Queue

• Priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it.
• In a priority queue, an element with high priority is served before an element with low priority.
• If two elements have the same priority, they are served according to their order in the queue.

2. Priority Queue Implementation in Python

The following python program 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]

3. Python Priority Queue Example

Let’s see an example of how to use above created priority queue.

class Item:
	def __init__(self, name):
		self.name = name
	def __repr__(self):
		return 'Item({!r})'.format(self.name)

>>> q = PriorityQueue()

>>> q.push(Item('how'), 1)
>>> q.push(Item('to'), 5)
>>> q.push(Item('do'), 4)
>>> q.push(Item('in'), 2)
>>> q.push(Item('java'), 1)

>>> q.pop()
Item('to')		#5

>>> q.pop()
Item('do')		#4

>>> q.pop()
Item('in')		#2

>>> q.pop()
Item('how')		#1

>>> q.pop()
Item('java')	#1

Happy Learning !!