PYTHON
Implement a Priority Queue for Task Scheduling
Create a priority queue in Python using the heapq module for efficient management of tasks, ensuring higher-priority items are processed first.
import heapq
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0 # Unique index for tie-breaking
def push(self, priority, item):
# Item format: (priority, index, item). Lower priority value means higher priority.
heapq.heappush(self._queue, (priority, self._index, item))
self._index += 1
def pop(self):
if not self._queue:
raise IndexError("pop from empty priority queue")
# Returns the item with the highest priority (lowest priority value)
return heapq.heappop(self._queue)[2] # Get the actual item
def is_empty(self):
return len(self._queue) == 0
# Example usage in a web context (e.g., background job queue)
task_queue = PriorityQueue()
task_queue.push(3, "Send low-priority email notification")
task_queue.push(1, "Process critical user payment")
task_queue.push(2, "Update user profile analytics")
task_queue.push(1, "Generate urgent report") # Same priority as payment, index will differentiate
print(f"Next task: {task_queue.pop()}") # Should be "Process critical user payment" or "Generate urgent report"
print(f"Next task: {task_queue.pop()}") # The other priority 1 task
print(f"Next task: {task_queue.pop()}") # "Update user profile analytics"
print(f"Next task: {task_queue.pop()}") # "Send low-priority email notification"
# print(task_queue.pop()) # Would raise IndexError
How it works: The `heapq` module implements the heap queue algorithm, which is a binary heap data structure. This snippet wraps `heapq` to create a simple priority queue. Tasks are pushed with a priority value (lower value = higher priority) and an auto-incrementing index for stable sorting of items with identical priorities. `pop()` always retrieves and removes the highest priority item efficiently.