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 !!
Was this post helpful?
Let us know if you liked the post. That’s the only way we can improve.