PYTHON
Implementing a Priority Queue with heapq
Learn to implement a priority queue (min-heap) in Python using the `heapq` module to efficiently retrieve the smallest item first, ideal for task scheduling.
import heapq
# A priority queue stores items, typically as (priority, item) tuples.
# heapq creates a min-heap, meaning the smallest item is always at index 0.
priority_queue = []
# Add items to the priority queue: heapq.heappush(heap, item)
# Lower priority number means higher priority.
heapq.heappush(priority_queue, (3, 'task C')) # Priority 3
heapq.heappush(priority_queue, (1, 'task A')) # Priority 1
heapq.heappush(priority_queue, (2, 'task B')) # Priority 2
heapq.heappush(priority_queue, (0, 'task X')) # Highest priority
print(f"Current priority queue (internal representation): {priority_queue}")
# Retrieve items by priority: heapq.heappop(heap)
# Always returns the item with the smallest priority.
highest_priority_task = heapq.heappop(priority_queue)
print(f"Popped: {highest_priority_task}")
next_highest_priority_task = heapq.heappop(priority_queue)
print(f"Popped: {next_highest_priority_task}")
# heappushpop pushes an item then pops the smallest (single operation)
smallest_after_push = heapq.heappushpop(priority_queue, (0, 'task Y - NEW'))
print(f"Push new task Y (priority 0) then pop smallest: {smallest_after_push}")
print(f"Remaining queue: {priority_queue}")
How it works: The `heapq` module provides an implementation of the heap queue algorithm, also known as the priority queue. It uses a list to represent the heap, maintaining the heap invariant (heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2]), ensuring the smallest element is always at index 0. `heappush` adds an item, and `heappop` removes and returns the smallest item, both efficiently. This is ideal for scheduling, event processing, and algorithms needing fast access to minimum/maximum elements.