PYTHON
Implement Min-Heaps and Priority Queues with Python's heapq Module
Master Python's heapq module to efficiently implement min-heaps, find the smallest/largest N elements, and build priority queues crucial for many optimization algorithms.
import heapq
# Initialize an empty list that will function as a min-heap
min_heap = []
# Push items onto the heap
heapq.heappush(min_heap, 4)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 7)
heapq.heappush(min_heap, 3)
print(f"Heap after pushes (not sorted visually, but min-heap property holds): {min_heap}")
# Pop the smallest item from the heap
smallest = heapq.heappop(min_heap)
print(f"Popped smallest: {smallest}, Heap remaining: {min_heap}")
# Replace smallest item with a new one (efficiently)
# Equivalent to heappop then heappush, but faster
next_smallest = heapq.heapreplace(min_heap, 2) # Pops 3, pushes 2
print(f"Replaced and popped: {next_smallest}, Heap remaining: {min_heap}")
# Find N largest/smallest items from an iterable
data = [1, 3, 5, 7, 2, 4, 6, 8, 0, 9]
n_smallest = heapq.nsmallest(3, data)
n_largest = heapq.nlargest(3, data)
print(f"3 smallest items from data: {n_smallest}")
print(f"3 largest items from data: {n_largest}")
How it works: The heapq module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. It treats a regular Python list as a min-heap, where the smallest element is always at index 0. heapq.heappush() adds an item while maintaining the heap invariant, and heapq.heappop() removes and returns the smallest item. This module is ideal for efficiently finding the smallest or largest N items from a collection or for implementing priority queues in algorithms like Dijkstra's or A*.