PYTHON
Implement Priority Queues and Find Top N Items with Python `heapq`
Discover how to use Python's `heapq` module to efficiently manage priority queues and extract the smallest or largest N elements from a collection, essential for task scheduling or ranking data.
import heapq
# Initialize an empty min-heap (list)
min_heap = []
# Add items to the heap (priority, item_name)
heapq.heappush(min_heap, (3, 'Task C'))
heapq.heappush(min_heap, (1, 'Task A'))
heapq.heappush(min_heap, (2, 'Task B'))
heapq.heappush(min_heap, (0, 'Task Z')) # Lower priority number means higher priority
# The smallest item (highest priority) is always at index 0
# However, the full heap property only guarantees heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2]
# not that it's fully sorted
# print(min_heap) # Example: [(0, 'Task Z'), (1, 'Task A'), (2, 'Task B'), (3, 'Task C')]
# Pop items from the heap (always retrieves the smallest/highest priority)
highest_priority_task = heapq.heappop(min_heap) # (0, 'Task Z')
next_highest_task = heapq.heappop(min_heap) # (1, 'Task A')
# Find the N smallest/largest items from an iterable
data = [10, 3, 7, 1, 9, 2, 8, 4, 6, 5]
top_3_smallest = heapq.nsmallest(3, data) # [1, 2, 3]
top_3_largest = heapq.nlargest(3, data) # [10, 9, 8]
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 regular list into a min-heap, ensuring that the smallest element is always at the root (index 0). This is particularly useful for efficiently retrieving the highest priority item, managing scheduled tasks, or finding the 'top N' smallest or largest elements from a dataset without fully sorting it.