PYTHON
Build a Priority Queue (Min-Heap) with Python's heapq Module
Implement a priority queue efficiently using Python's heapq module, a min-heap data structure, for tasks requiring processing items based on their priority or finding the smallest elements.
import heapq
# A list to be used as a min-heap
# In Python, heapq functions work on regular lists.
# The list itself is not a heap object, but functions treat it as one.
min_heap = []
print(f"Initial heap: {min_heap}")
# Push items onto the heap. Push takes O(log n) time.
# Items are typically tuples (priority, value) for priority queues.
heapq.heappush(min_heap, (3, 'task_C'))
heapq.heappush(min_heap, (1, 'task_A'))
heapq.heappush(min_heap, (4, 'task_D'))
heapq.heappush(min_heap, (2, 'task_B'))
print(f"Heap after pushes: {min_heap}") # Note: The list isn't strictly sorted, only the root is the smallest
# Pop the smallest item from the heap. Pop also takes O(log n) time.
# The smallest item is always at index 0.
first_priority_item = heapq.heappop(min_heap)
print(f"Popped: {first_priority_item}, Remaining heap: {min_heap}")
second_priority_item = heapq.heappop(min_heap)
print(f"Popped: {second_priority_item}, Remaining heap: {min_heap}")
# Example: Find the 3 smallest elements from a list without fully sorting
data = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
smallest_3 = heapq.nsmallest(3, data)
print(f"Smallest 3 elements from data: {smallest_3}")
How it works: The `heapq` module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. It allows you to use regular Python lists as min-heaps, meaning the smallest element is always at index 0. `heappush` adds an item while maintaining the heap invariant, and `heappop` removes and returns the smallest item. This is efficient for scenarios where you need to continuously extract the highest-priority (smallest-value) item without sorting the entire collection, such as task schedulers, event simulations, or finding N smallest/largest items.