PYTHON
Building Priority Queues with Python's heapq Module
Learn to implement min-heap based priority queues efficiently using Python's heapq module, essential for tasks requiring smallest-first retrieval in O(log n) time.
import heapq
# Initialize a min-heap (Python's heapq is a min-heap by default)
priority_queue = []
# Push items onto the heap (item, priority). For a min-heap,
# the smallest priority value will be treated as higher priority.
# To store (priority, item), priority comes first.
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
print(f"Heap after pushes: {priority_queue}")
# Pop the smallest item (highest priority)
highest_priority_item = heapq.heappop(priority_queue)
print(f"Popped item: {highest_priority_item}, Heap remaining: {priority_queue}")
# Push another item
heapq.heappush(priority_queue, (0, 'task Z')) # even higher priority
print(f"Heap after another push: {priority_queue}")
# Pop again
next_item = heapq.heappop(priority_queue)
print(f"Popped item: {next_item}, Heap remaining: {priority_queue}")
# Heapify an existing list (in-place)
data = [5, 1, 9, 4, 7]
heapq.heapify(data)
print(f"Heapified list: {data}")
# Get the three smallest items without modifying the heap
print(f"Three smallest items: {heapq.nsmallest(3, data)}")
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, meaning the smallest element is always at the root. heappush() adds an item maintaining the heap invariant, and heappop() removes and returns the smallest item, both in O(log n) time. It's ideal for tasks like event scheduling, shortest path algorithms, or always retrieving the smallest (or largest with a trick using negative priorities) element efficiently.