PYTHON
Manage Priority Queues and Top N Elements with Heapq
Learn to use Python's heapq module to efficiently implement priority queues or quickly find the N smallest or largest items from a collection.
import heapq
# --- Priority Queue Example ---
# A min-heap by default. Elements are pushed as (priority, item) tuples.
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'))
# Pop items, smallest priority first
# print(f"Next task (highest priority): {heapq.heappop(priority_queue)}") # (1, 'High priority task')
# print(f"Next task: {heapq.heappop(priority_queue)}") # (2, 'Medium priority task')
# --- Find N Largest/Smallest Elements ---
data = [1, 5, 2, 9, 3, 7, 6, 8, 4]
# Find the 3 smallest elements
smallest_three = heapq.nsmallest(3, data)
# print(f"3 Smallest elements: {smallest_three}") # [1, 2, 3]
# Find the 3 largest elements
largest_three = heapq.nlargest(3, data)
# print(f"3 Largest elements: {largest_three}") # [9, 8, 7]
# Heaps can also be built from an existing list in-place
unsorted_list = [5, 1, 9, 3, 7, 2, 8, 4, 6]
heapq.heapify(unsorted_list) # Transforms list into a heap (in-place)
# print(f"Heapified list: {unsorted_list}") # [1, 3, 2, 4, 7, 5, 8, 9, 6] (Order not strictly sorted, just heap property)
How it works: The heapq module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. It allows you to push and pop elements while maintaining the heap invariant (smallest element always at the root). This is highly efficient for implementing priority queues or quickly finding the N smallest or largest elements from a collection without fully sorting it.