PYTHON
Building a Priority Queue in Python with `heapq`
Discover how to efficiently implement a min-priority queue in Python using the `heapq` module. Ideal for algorithms needing fast retrieval of the smallest element.
import heapq
# Create an empty min-heap
priority_queue = []
# Add elements to the priority queue
# heapq stores elements as a min-heap, so the smallest element is always at index 0.
# For a max-heap, store (negative priority, item).
heapq.heappush(priority_queue, (3, 'task_low_priority'))
heapq.heappush(priority_queue, (1, 'task_high_priority'))
heapq.heappush(priority_queue, (2, 'task_medium_priority'))
heapq.heappush(priority_queue, (1, 'task_critical')) # Same priority, order might vary
print(f"Priority Queue (internal representation): {priority_queue}")
# Retrieve and remove the smallest element (highest priority)
while priority_queue:
priority, task = heapq.heappop(priority_queue)
print(f"Processing task: '{task}' with priority: {priority}")
# Using heappushpop for efficiency (push then pop smallest)
new_pq = []
heapq.heappush(new_pq, 5)
heapq.heappush(new_pq, 2)
smallest_after_push = heapq.heappushpop(new_pq, 1) # Pushes 1, then pops the smallest (1)
print(f"Smallest after heappushpop: {smallest_after_push}, remaining: {new_pq}")
How it works: The `heapq` module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. It uses a binary min-heap structure, meaning the smallest element is always at the root (index 0). `heappush` adds an element while maintaining the heap invariant, and `heappop` extracts and removes the smallest item. This makes it highly efficient for scenarios where you need to repeatedly access the smallest (or largest, with a trick) item from a collection, such as Dijkstra's algorithm or event schedulers.