PYTHON
Manage Priority Queues and Top N Items with Heapq
Learn to use Python's `heapq` module to implement min-heaps, ideal for efficiently retrieving the smallest items, managing priority queues, or finding the 'top N' largest/smallest elements in a collection.
import heapq
# Example 1: Basic min-heap operations
data = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(data) # Transform list into a heap (in-place)
print(f"Heapified data (internal representation, not sorted): {data}")
smallest = heapq.heappop(data) # Remove and return the smallest item
print(f"Smallest item: {smallest}, remaining heap: {data}")
heapq.heappush(data, 0) # Add a new item to the heap
print(f"After pushing 0: {data}")
next_smallest = heapq.heappop(data)
print(f"Next smallest item: {next_smallest}, remaining heap: {data}")
# Example 2: Finding the N smallest items (min-heap behavior)
numbers = [10, 4, 8, 12, 1, 5, 9, 2, 7, 6, 3, 11]
three_smallest = heapq.nsmallest(3, numbers)
print(f"Three smallest numbers: {three_smallest}")
# Example 3: Finding the N largest items (using nlargest)
three_largest = heapq.nlargest(3, numbers)
print(f"Three largest numbers: {three_largest}")
# Example 4: Priority Queue (simulated)
# Store items as (priority, item) tuples; heapq sorts by the first element (priority)
priority_queue = []
heapq.heappush(priority_queue, (3, "Low priority task"))
heapq.heappush(priority_queue, (1, "High priority task"))
heapq.heappush(priority_queue, (2, "Medium priority task"))
while priority_queue:
priority, task = heapq.heappop(priority_queue)
print(f"Processing task with priority {priority}: {task}")
How it works: The `heapq` module implements the heap queue algorithm, also known as the priority queue algorithm. It uses a min-heap structure, meaning the smallest element is always at the root. This module is incredibly useful for efficiently retrieving the smallest (or largest with `nlargest`) items from a collection, managing priority queues where tasks need to be processed based on their urgency, or implementing "top N" features for leaderboards or trending items in web applications without fully sorting the entire dataset.