PYTHON
Implementing a Priority Queue with Python's `heapq` Module
Learn how to create an efficient priority queue in Python using the built-in `heapq` module, essential for tasks like scheduling and shortest path algorithms.
import heapq
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
# Items are tuples of (-priority, index, item)
# We use -priority because heapq is a min-heap.
# index is used to ensure stable sorting for items with same priority.
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
if not self._queue:
raise IndexError("Cannot pop from an empty priority queue")
# Returns the item with the highest priority
return heapq.heappop(self._queue)[-1]
def is_empty(self):
return not bool(self._queue)
# Example Usage:
pq = PriorityQueue()
pq.push("Task A", 3)
pq.push("Task B", 1)
pq.push("Task C", 2)
pq.push("Task D", 3) # Same priority as Task A, will be popped after A due to stable sorting
results = []
while not pq.is_empty():
results.append(pq.pop())
# Expected output: ['Task A', 'Task D', 'Task C', 'Task B']
# (Order for same priority might depend on insertion order / stable sort index)
# With index for stable sort: Task A, Task D, Task C, Task B
# print(results)
How it works: This snippet demonstrates how to build a priority queue using Python's `heapq` module. The `heapq` module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. By storing items as tuples `(-priority, index, item)`, we ensure that `heapq` (a min-heap) correctly retrieves items with the *highest* priority first. The `_index` ensures stable sorting for items with identical priorities.