PYTHON
Managing Priority Queues with Python's `heapq` Module
Utilize Python's `heapq` module to implement efficient min-priority queues, enabling quick access to the smallest element and maintaining heap invariants.
import heapq
# Initialize a list as a heap (min-heap by default)
# The smallest element is always at index 0
min_heap = []
# Push elements onto the heap
heapq.heappush(min_heap, 4)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 7)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 2)
print(f"Heap after pushes: {min_heap}") # Not sorted, but heap property maintained
# Pop the smallest element
smallest = heapq.heappop(min_heap)
print(f"Popped smallest element: {smallest}")
print(f"Heap after pop: {min_heap}")
# Another pop
next_smallest = heapq.heappop(min_heap)
print(f"Popped next smallest element: {next_smallest}")
print(f"Heap after second pop: {min_heap}")
# Convert an existing list into a heap in-place
data = [5, 1, 9, 4, 7, 2]
heapq.heapify(data)
print(f"List after heapify: {data}")
# Use heappop on the heapified list
print(f"Popping from heapified list: {heapq.heappop(data)}")
print(f"Heapified list after pop: {data}")
# N-largest or N-smallest elements without fully sorting
numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(f"
3 largest numbers: {heapq.nlargest(3, numbers)}")
print(f"3 smallest numbers: {heapq.nsmallest(3, numbers)}")
How it works: The `heapq` module in Python provides an implementation of the heap queue algorithm, also known as the priority queue. It uses a min-heap structure, where the smallest element is always at the root (index 0). This module is highly efficient for tasks like finding the k-th smallest/largest element, implementing priority queues in algorithms (e.g., Dijkstra's, A*), and managing event queues in simulations or scheduling systems.