PYTHON
Implement Priority Queues and Find K-elements with Heapq
Master Python's heapq module to efficiently manage priority queues and find the K smallest or largest elements in a collection, vital for task scheduling and data ranking.
import heapq
# Example 1: Implementing a min-priority queue
# Elements are (priority, item) tuples; heapq sorts by the first element (priority)
min_pq = []
heapq.heappush(min_pq, (3, "Task A: Low priority"))
heapq.heappush(min_pq, (1, "Task B: High priority"))
heapq.heappush(min_pq, (2, "Task C: Medium priority"))
heapq.heappush(min_pq, (0, "Task D: Critical priority"))
print("Processing tasks by priority (min-heap):")
while min_pq:
priority, task = heapq.heappop(min_pq)
print(f"Processing task '{task}' with priority {priority}")
print("-" * 20)
# Example 2: Finding the K smallest elements
data = [10, 4, 1, 8, 15, 7, 3, 12, 6, 9]
k = 3
smallest_k_elements = heapq.nsmallest(k, data)
print(f"{k} smallest elements: {smallest_k_elements}")
# Example 3: Finding the K largest elements
largest_k_elements = heapq.nlargest(k, data)
print(f"{k} largest elements: {largest_k_elements}")
How it works: The `heapq` module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm, using a regular Python list. `heapq.heappush()` adds an item while maintaining the heap invariant (smallest item at index 0), and `heapq.heappop()` efficiently removes and returns the smallest item. For finding the `k` smallest or largest items efficiently without sorting the entire list, `heapq.nsmallest()` and `heapq.nlargest()` are extremely useful. This is crucial for scenarios like task scheduling, finding leaderboards, or analyzing top/bottom values in web services.