PYTHON
Manage Priority Queues and Find Extremes with `heapq`
Utilize Python's `heapq` module to implement efficient min-heaps, ideal for priority queues, scheduling tasks, or quickly finding the N smallest or largest elements in a collection.
import heapq
# Basic min-heap operations (priority queue)
priority_queue = [] # Standard list acts as the heap
heapq.heappush(priority_queue, (2, "Task B")) # (priority, item)
heapq.heappush(priority_queue, (1, "Task A"))
heapq.heappush(priority_queue, (3, "Task C"))
print(f"Initial priority queue: {priority_queue}")
print(f"Next task: {heapq.heappop(priority_queue)}") # Popping lowest priority (1, "Task A")
print(f"Next task: {heapq.heappop(priority_queue)}") # Popping next lowest priority (2, "Task B")
print(f"Queue after pops: {priority_queue}")
# Finding N smallest elements from a list
data = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
smallest_3 = heapq.nsmallest(3, data)
print(f"3 smallest elements: {smallest_3}") # Output: [-4, 1, 2]
# Finding N largest elements from a list
largest_3 = heapq.nlargest(3, data)
print(f"3 largest elements: {largest_3}") # Output: [42, 37, 23]
# Using a key function with nsmallest/nlargest (e.g., by length)
words = ["apple", "banana", "kiwi", "grapefruit", "fig"]
shortest_2 = heapq.nsmallest(2, words, key=len)
print(f"2 shortest words: {shortest_2}") # Output: ['fig', 'kiwi']
How it works: The `heapq` module implements the heap queue algorithm, also known as the priority queue algorithm. It uses a regular Python list to maintain a heap invariant: `heap[k] <= heap[2*k+1]` and `heap[k] <= heap[2*k+2]` for all `k`. This means the smallest element is always at index 0. `heappush` adds an item while maintaining the invariant, and `heappop` removes and returns the smallest item efficiently. `nsmallest` and `nlargest` functions provide convenient ways to retrieve the extreme N elements without fully sorting the entire collection.