PYTHON
Efficient Priority Queue Management with `heapq`
Learn to use Python's `heapq` module to efficiently manage priority queues, allowing quick access to the smallest element. Ideal for task scheduling or finding k-th smallest items.
import heapq
# Initialize a min-heap
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 4)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 5)
print(f"Min-heap elements: {min_heap}") # Internal representation is not sorted, but heap property holds
# Get the smallest element
smallest = heapq.heappop(min_heap)
print(f"Popped smallest element: {smallest}")
print(f"Min-heap after pop: {min_heap}")
# Implementing a max-heap (negate values)
max_heap = []
tasks = [(1, 'Task A'), (3, 'Task B'), (2, 'Task C')] # (priority, item)
for priority, item in tasks:
heapq.heappush(max_heap, (-priority, item)) # Store negated priority
print(f"Max-heap elements (internal): {max_heap}")
# Get the largest priority element
highest_priority_task = heapq.heappop(max_heap)
print(f"Popped highest priority task: {highest_priority_task[1]} (Priority: {-highest_priority_task[0]})")
print(f"Max-heap after pop: {max_heap}")
How it works: The `heapq` module implements the heap queue algorithm, also known as the priority queue algorithm. It provides functions to efficiently add and retrieve the smallest element from a collection. By default, `heapq` creates a min-heap. To simulate a max-heap, elements can be pushed and popped by negating their priority values, allowing the largest original priority to be treated as the smallest negated value.