PYTHON
Manage Priority Queues and Find Extremes with Python `heapq`
Leverage Python's `heapq` module to implement min-heaps, useful for priority queues, finding the N smallest or largest elements efficiently, and managing event scheduling.
import heapq
# Create a min-heap
data = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(data) # In-place transformation to a heap
print(f"Min-heap: {data}")
# Push elements
heapq.heappush(data, 0)
print(f"Heap after push(0): {data}")
# Pop smallest element
smallest = heapq.heappop(data)
print(f"Popped smallest: {smallest}, Heap: {data}")
# Get N smallest elements
list_of_items = [10, 2, 8, 1, 5, 9, 3]
n_smallest = heapq.nsmallest(3, list_of_items)
print(f"3 smallest elements: {n_smallest}")
# Get N largest elements
n_largest = heapq.nlargest(2, list_of_items)
print(f"2 largest elements: {n_largest}")
# Example: Priority Queue (tuples can be used for priority)
priority_queue = []
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"Processing priority queue:")
while priority_queue:
priority, item = heapq.heappop(priority_queue)
print(f" Priority: {priority}, Item: {item}")
How it works: The `heapq` module in Python provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. It allows you to transform a list into a min-heap in-place (`heapify`), efficiently push new elements while maintaining the heap property (`heappush`), and retrieve the smallest element (`heappop`). It's excellent for finding the N smallest/largest elements without fully sorting, and for implementing priority queues where elements are processed based on their priority, crucial for task scheduling or resource management in web services.