PYTHON
Implement a Min-Heap (Priority Queue) with Python's heapq
Learn to use Python's `heapq` module to create a min-heap, effectively implementing a priority queue for scenarios where you need to efficiently retrieve and manage the smallest element.
import heapq
# Initialize an empty min-heap
min_heap = []
# Add elements to 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 pushing elements: {min_heap}") # Note: internal representation is not fully sorted
# Get and remove the smallest element (root of the heap)
smallest = heapq.heappop(min_heap)
print(f"Smallest element popped: {smallest}")
print(f"Heap after pop: {min_heap}")
# Push another element
heapq.heappush(min_heap, 0)
print(f"Heap after pushing 0: {min_heap}")
# Get the new smallest element
new_smallest = heapq.heappop(min_heap)
print(f"New smallest element popped: {new_smallest}")
print(f"Heap after pop: {min_heap}")
# Heapify an existing list (in-place transformation)
existing_list = [5, 2, 8, 1, 9, 4]
heapq.heapify(existing_list)
print(f"Heapified list: {existing_list}")
# Finding N largest/smallest elements (without modifying original list if desired)
largest_3 = heapq.nlargest(3, [10, 20, 5, 15, 25, 30])
smallest_3 = heapq.nsmallest(3, [10, 20, 5, 15, 25, 30])
print(f"3 largest elements: {largest_3}")
print(f"3 smallest elements: {smallest_3}")
How it works: The `heapq` module in Python provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. It uses a list as the underlying data structure, maintaining the heap invariant (min-heap: parent is always smaller than or equal to its children). This snippet demonstrates `heappush` to add elements, `heappop` to retrieve and remove the smallest element efficiently, and `heapify` to convert an existing list into a heap. It also shows `nlargest` and `nsmallest` for quickly finding extreme values.