Priority Queue Basics

You're building an emergency room system. Patients arrive constantly. But you can't treat them first-come-first-served. A heart attack patient needs treatment before someone with a minor cut, even if the cut patient arrived first.

You need priority-based ordering. Not FIFO, not LIFO. Priority.

That's a priority queue.

What's a Priority Queue?

An abstract data type. Elements have priorities. Higher priority elements come out first, regardless of insertion order.

Operations:

• Insert: Add element with priority
• Extract max/min: Remove and return highest/lowest priority element
• Peek: Look at highest/lowest priority without removing

import heapq

# Python's heapq implements min priority queue
pq = []

heapq.heappush(pq, (1, "Low priority task"))
heapq.heappush(pq, (10, "High priority task"))
heapq.heappush(pq, (5, "Medium priority task"))

priority, task = heapq.heappop(pq)
print(task)  # "Low priority task" (lowest priority number = highest urgency)

Not a queue in the FIFO sense. It's priority-ordered.

Why Priority Queues?

Event-driven simulation: Events have timestamps. Process earliest event next.

Task scheduling: CPU scheduler. High priority tasks run first.

Graph algorithms: Dijkstra's shortest path, Prim's MST. Always process node with smallest distance.

Data compression: Huffman coding. Build tree by combining lowest-frequency nodes.

Priority Queue vs Regular Queue

Regular queue: fair but ignores urgency.
Priority queue: handles urgency but doesn't preserve insertion order for same priority.

Max vs Min Priority Queue

Max priority queue: Highest priority (largest value) comes out first.

# Simulate max heap with negative values
max_pq = []
heapq.heappush(max_pq, -10)  # Priority 10
heapq.heappush(max_pq, -5)   # Priority 5
heapq.heappush(max_pq, -20)  # Priority 20

max_priority = -heapq.heappop(max_pq)
print(max_priority)  # 20

Min priority queue: Lowest priority (smallest value) comes out first.

min_pq = []
heapq.heappush(min_pq, 10)
heapq.heappush(min_pq, 5)
heapq.heappush(min_pq, 20)

min_priority = heapq.heappop(min_pq)
print(min_priority)  # 5

Choose based on what "priority" means. Shortest deadline? Min. Highest importance score? Max.

Example: Hospital Triage

import heapq

class Patient:
    def __init__(self, name, severity):
        self.name = name
        self.severity = severity  # 1-10, higher = more severe
    
    def __lt__(self, other):
        # Higher severity = higher priority (comes out first)
        return self.severity > other.severity

pq = []

heapq.heappush(pq, Patient("Alice", 3))   # Minor
heapq.heappush(pq, Patient("Bob", 9))     # Critical
heapq.heappush(pq, Patient("Charlie", 5)) # Moderate

while pq:
    patient = heapq.heappop(pq)
    print(f"Treating {patient.name} (severity {patient.severity})")

# Output:
# Treating Bob (severity 9)
# Treating Charlie (severity 5)
# Treating Alice (severity 3)

Bob (critical) treated first, even though Alice arrived first.

Implementation Choices

Unsorted array:

• Insert: O(1) (just append)
• Extract: O(n) (scan for max/min)

Sorted array:

• Insert: O(n) (find position, shift)
• Extract: O(1) (take first/last)

Heap (binary heap):

• Insert: O(log n)
• Extract: O(log n)

Heap wins for most use cases. Balanced performance.

Example: Task Scheduler

import heapq
from collections import namedtuple

Task = namedtuple('Task', ['priority', 'name'])

scheduler = []

# Add tasks (lower number = higher priority)
heapq.heappush(scheduler, Task(1, "Critical bug fix"))
heapq.heappush(scheduler, Task(3, "Code review"))
heapq.heappush(scheduler, Task(2, "Deploy feature"))
heapq.heappush(scheduler, Task(1, "Security patch"))

while scheduler:
    task = heapq.heappop(scheduler)
    print(f"Processing: {task.name} (priority {task.priority})")

# Output:
# Processing: Critical bug fix (priority 1)
# Processing: Security patch (priority 1)
# Processing: Deploy feature (priority 2)
# Processing: Code review (priority 3)

Tasks with priority 1 processed first. Among same priority, insertion order (or use counter for tie-breaking).

Tie-Breaking

What if two elements have same priority?

Option 1: Don't care (undefined order).

Option 2: Use counter (preserve insertion order).

import heapq

class PriorityQueue:
    def __init__(self):
        self.pq = []
        self.counter = 0
    
    def push(self, priority, item):
        # (priority, counter, item)
        # Counter ensures FIFO for same priority
        heapq.heappush(self.pq, (priority, self.counter, item))
        self.counter += 1
    
    def pop(self):
        if not self.pq:
            raise IndexError("Empty queue")
        priority, _, item = heapq.heappop(self.pq)
        return item

pq = PriorityQueue()
pq.push(1, "Task A")
pq.push(1, "Task B")
pq.push(1, "Task C")

print(pq.pop())  # "Task A" (first with priority 1)
print(pq.pop())  # "Task B"
print(pq.pop())  # "Task C"

Counter guarantees insertion order for ties.

The Abstraction

Priority queue is an interface, not an implementation:

• Interface: insert, extract max/min, peek
• Implementation: heap (most common), sorted array, BST, etc.

Most languages provide heap-based priority queue in standard library.

Understanding priority queues means knowing:

• When to use priority over FIFO
• How priorities determine order
• Trade-offs of different implementations

Master priority queues, and you'll handle event-driven and scheduling problems efficiently.