PYTHON
Implement Min-Heap (Priority Queue) with Python's heapq
Efficiently manage a priority queue or find the smallest elements using Python's heapq module, which implements the heap queue algorithm. Ideal for scheduling and graph traversals.
import heapq
# Create an empty min-heap (represented as a list)
min_heap = []
# Add elements to the heap (heappush maintains heap property)
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: {min_heap}") # Note: internal list order may not be sorted
# Pop the smallest element (heappop removes and returns the smallest)
smallest = heapq.heappop(min_heap)
print(f"Smallest element popped: {smallest}, Heap: {min_heap}")
smallest = heapq.heappop(min_heap)
print(f"Next smallest element popped: {smallest}, Heap: {min_heap}")
# Peek at the smallest element without removing it
if min_heap:
print(f"Peek smallest (without pop): {min_heap[0]}")
# Convert an existing list into a heap in-place
my_list = [5, 2, 8, 0, 6]
heapq.heapify(my_list)
print(f"List after heapify: {my_list}")
# Find the N largest/smallest elements efficiently
data = [10, 20, 5, 30, 15, 25]
print(f"3 largest elements from data: {heapq.nlargest(3, data)}")
print(f"3 smallest elements from data: {heapq.nsmallest(3, data)}")
How it works: Python's `heapq` module provides an implementation of the min-heap data structure, also known as a priority queue. It works by treating a standard Python list as a heap, where the smallest element is always at index 0. `heappush` adds an element while maintaining the heap invariant, and `heappop` efficiently removes and returns the smallest item. This module is crucial for algorithms that require efficient retrieval of minimum or maximum elements, such as Dijkstra's algorithm or top-N element selection.