PYTHON
Priority Queue for Task Scheduling with heapq
Discover how to implement a priority queue in Python using the `heapq` module. This snippet demonstrates adding tasks with priorities and extracting them in order, ideal for managing scheduled jobs or event processing in web services.
import heapq
import itertools
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = itertools.count() # Unique sequence numbers for tie-breaking
def push(self, priority, item):
# Items are tuples: (priority, tie_breaker, item)
# heapq is min-heap, so lower priority values come first.
heapq.heappush(self._queue, (priority, next(self._index), item))
def pop(self):
if not self._queue:
raise IndexError("pop from empty priority queue")
# Pop returns the smallest item, which is the highest priority (lowest priority number)
priority, _, item = heapq.heappop(self._queue)
return item, priority
def peek(self):
if not self._queue:
raise IndexError("peek from empty priority queue")
priority, _, item = self._queue[0]
return item, priority
def is_empty(self):
return not bool(self._queue)
# Example Usage:
# task_queue = PriorityQueue()
# task_queue.push(3, 'Low priority task')
# task_queue.push(1, 'High priority task')
# task_queue.push(2, 'Medium priority task 1')
# task_queue.push(2, 'Medium priority task 2') # Same priority, tie-breaker used
# print("Tasks in priority order:")
# while not task_queue.is_empty():
# task, prio = task_queue.pop()
# print(f" Priority {prio}: {task}")
# Expected output:
# Priority 1: High priority task
# Priority 2: Medium priority task 1 (or 2, depends on tie-breaker)
# Priority 2: Medium priority task 2 (or 1)
# Priority 3: Low priority task
How it works: This snippet demonstrates a `PriorityQueue` implementation using Python's `heapq` module, which maintains a min-heap. Tasks are pushed with an associated priority (lower number means higher priority). A `_index` from `itertools.count()` is used as a tie-breaker for items with the same priority, ensuring stable sorting and correct behavior. The `pop` method always retrieves the highest priority item, making it ideal for managing tasks, event loops, or job queues in web applications.