PYTHON
Implement Priority Queues with heapq Module
Learn how to use Python's heapq module to create min-heaps, effectively implementing a priority queue for tasks like scheduling, event processing, or managing job queues based on priority.
import heapq
# A list can be treated as a heap.
# heapq operations maintain the heap invariant (min-heap by default).
priority_queue = []
# Add items to the priority queue (priority, item)
# Lower priority number means higher priority
heapq.heappush(priority_queue, (3, 'Low priority task'))
heapq.heappush(priority_queue, (1, 'High priority task'))
heapq.heappush(priority_queue, (2, 'Medium priority task'))
heapq.heappush(priority_queue, (1, 'Another high priority task'))
print(f"Current priority queue (raw heap): {priority_queue}")
# Retrieve and remove the smallest item (highest priority)
next_task_priority, next_task_name = heapq.heappop(priority_queue)
print(f"Next task: {next_task_name} (Priority: {next_task_priority})")
next_task_priority, next_task_name = heapq.heappop(priority_queue)
print(f"Next task: {next_task_name} (Priority: {next_task_priority})")
print(f"Priority queue after pops: {priority_queue}")
# Building a heap from existing data
data = [(5, 'Task E'), (1, 'Task A'), (3, 'Task C'), (2, 'Task B'), (4, 'Task D')]
heapq.heapify(data)
print(f"Heapified data: {data}")
How it works: The heapq module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. It allows efficient retrieval of the smallest element (or largest, with a small trick). This is invaluable for managing tasks by priority, scheduling events, or implementing algorithms like Dijkstra's. It operates on regular Python lists, treating them as heaps.