Priority Queue — Junior Level¶

One-line summary: A priority queue is an abstract data type (ADT) that hands you items in priority order rather than FIFO order. The most common implementation is a binary heap, but the interface — push, pop-highest-priority, peek — is what defines a priority queue, not the data structure underneath it.

Table of Contents¶

1. Introduction
2. Prerequisites
3. Glossary
4. Core Concepts
5. Big-O Summary
6. Real-World Analogies
7. Pros & Cons
8. Choosing an Implementation
9. Code Examples
10. Coding Patterns
11. Error Handling
12. Performance Tips
13. Best Practices
14. Edge Cases & Pitfalls
15. Common Mistakes
16. Cheat Sheet
17. Visual Animation
18. Summary
19. Further Reading

Introduction¶

A normal queue is first-in, first-out: the order things come out is the order they went in. A priority queue is highest-priority-out: the order things come out is determined by an importance value attached to each item.

It is one of the most common ADTs in computer science precisely because real life rarely respects insertion order. An operating system runs the most urgent task first. A hospital sees the most critical patient first. Dijkstra's algorithm processes the closest unsettled node first. A Kafka consumer with retry priorities pulls failed messages back into the front of the line.

The critical mental shift at this stage: priority queue is an interface, not a data structure. Five different data structures (binary heap, sorted array, BST, skip list, Fibonacci heap) all support the same push / pop-min / peek operations with very different time-and-space trade-offs. Picking one is part of your job as a programmer.

In practice, "priority queue" without qualification almost always means "binary-heap-backed priority queue" — heapq in Python, PriorityQueue in Java, container/heap in Go, std::priority_queue in C++. That binding is so strong that many programmers conflate the two. Try to keep them separate in your head: heaps are one way to build a priority queue, the way most often used because it's simple and fast.

Prerequisites¶

• Queue ADT — FIFO order: enqueue, dequeue.
• Stack ADT — LIFO order, for contrast.
• Big-O notation — O(1), O(log n), O(n).
• Binary heap (see ../01-binary-heap/junior.md) — the default implementation.
• Basic comparison operators — <, > and the idea of a comparator function.

Helpful but not required:

• BST and sorted-list mental model.
• Knowledge that "priority" in CS is lower-value-comes-first by convention (min-heap), unless explicitly inverted.

Glossary¶

Core Concepts¶

1. PQ is an interface¶

push(item, priority)          # add an item
pop()                          # return + remove highest-priority item
peek()                         # return highest-priority item without removing
size(), empty()

That's it. Any data structure that provides those four operations is a priority queue, no matter how it's built inside.

2. Priority order: min or max¶

By convention in algorithm textbooks, "highest priority" = "smallest priority value." Lower numbers mean more urgent. This is consistent with shortest-distance dictionaries: smaller dist = process sooner.

Min-PQ:   pop() returns the item with the smallest priority key.
Max-PQ:   pop() returns the item with the largest priority key.

If your library only gives you a min-PQ but you need a max-PQ, the two standard tricks are:

• Push -priority instead of priority (works for numeric keys).
• Pass a reversed comparator: (a, b) → b.priority - a.priority.

3. Storing the priority with the item¶

Most PQs store (priority, item) pairs or use a comparator that knows how to extract the priority. The item is the payload; the priority is the key.

push((dist, node_id))
priority, node_id = pop()

A subtle pitfall: if Python's heapq compares two pairs whose first elements are equal, it goes on to compare the second elements. If those are objects without an __lt__ method, you get a TypeError. The fix is the tiebreaker counter pattern: (priority, counter, item) — the counter guarantees the second component always orders.

4. Stability¶

A priority queue is stable if items with equal priority come out in the same order they went in. Binary heaps are not stable by themselves. To make them stable, you push (priority, counter, item); the counter is an ever-increasing integer.

heappush(pq, (priority, next_counter(), item))

5. Indexed PQ for decrease-key¶

When the priority of an existing item can change (Dijkstra finds a shorter path mid-run), you need:

decrease_key(item, new_priority)

To support this in O(log n), the PQ must remember where each item lives inside its underlying structure. That's an indexed PQ. See middle.md for the implementation.

Big-O Summary¶

Different implementations dominate on different operation mixes — that's the whole point of treating PQ as an ADT.

Real-World Analogies¶

Where the analogy breaks: in a real hospital you re-prioritise dozens of patients at once; most heap-backed PQs are happiest doing one mutation at a time.

Pros & Cons¶

When to use: anywhere "process the most important next" is the natural verb — schedulers, search algorithms, simulators, retry queues, message brokers with priority classes.

When NOT to use: strict FIFO (use a plain queue), bounded integer priorities with high QPS (consider a bucket / radix PQ), or read-heavy "search by value" (heap is O(n) for that).

Choosing an Implementation¶

Code Examples¶

Example 1: Using the language library¶

Go¶

package main

import (
    "container/heap"
    "fmt"
)

// Int-priority min-PQ on a custom Item type.
type Item struct {
    name     string
    priority int
    index    int             // position in heap (for decrease-key, optional)
}

type PQ []*Item

func (pq PQ) Len() int            { return len(pq) }
func (pq PQ) Less(i, j int) bool  { return pq[i].priority < pq[j].priority }
func (pq PQ) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i]; pq[i].index = i; pq[j].index = j }
func (pq *PQ) Push(x interface{}) { it := x.(*Item); it.index = len(*pq); *pq = append(*pq, it) }
func (pq *PQ) Pop() interface{} {
    old := *pq
    n := len(old)
    it := old[n-1]
    *pq = old[:n-1]
    return it
}

func main() {
    pq := &PQ{}
    heap.Init(pq)
    heap.Push(pq, &Item{name: "patch", priority: 3})
    heap.Push(pq, &Item{name: "deploy", priority: 1})
    heap.Push(pq, &Item{name: "lint", priority: 2})
    for pq.Len() > 0 {
        it := heap.Pop(pq).(*Item)
        fmt.Println(it.priority, it.name)
    }
    // 1 deploy
    // 2 lint
    // 3 patch
}

Java¶

import java.util.*;

public class PQExample {
    record Job(String name, int priority) {}

    public static void main(String[] args) {
        PriorityQueue<Job> pq = new PriorityQueue<>(Comparator.comparingInt(Job::priority));
        pq.add(new Job("patch", 3));
        pq.add(new Job("deploy", 1));
        pq.add(new Job("lint", 2));
        while (!pq.isEmpty()) {
            Job j = pq.poll();
            System.out.println(j.priority() + " " + j.name());
        }
    }
}

Python¶

import heapq
import itertools

class PriorityQueue:
    """Heap-backed PQ with stable ordering via a counter."""

    def __init__(self):
        self._data = []
        self._counter = itertools.count()

    def push(self, item, priority):
        heapq.heappush(self._data, (priority, next(self._counter), item))

    def pop(self):
        priority, _, item = heapq.heappop(self._data)
        return priority, item

    def peek(self):
        priority, _, item = self._data[0]
        return priority, item

    def __len__(self):
        return len(self._data)


pq = PriorityQueue()
pq.push("patch", 3)
pq.push("deploy", 1)
pq.push("lint", 2)
while len(pq):
    print(*pq.pop())
# 1 deploy
# 2 lint
# 3 patch

What it does: inserts three jobs with priorities and prints them in ascending priority order. Run: go run main.go | javac PQExample.java && java PQExample | python pq.py

Coding Patterns¶

Pattern 1: Top-K with a bounded PQ¶

Intent: Keep only the k smallest items in a stream. Use a max-PQ of size k; whenever the new item is smaller than the current max, evict and replace.

import heapq

def top_k_smallest(stream, k):
    h = []                          # min-heap of negated values to fake max-heap
    for x in stream:
        if len(h) < k:
            heapq.heappush(h, -x)
        elif -x > h[0]:             # x < current max
            heapq.heapreplace(h, -x)
    return sorted(-v for v in h)

Pattern 2: Tiebreaker stability¶

heapq.heappush(pq, (priority, next(counter), payload))

Without the counter, Python compares payloads when priorities tie — and crashes if payloads are not orderable.

Pattern 3: Delayed jobs (priority = deadline)¶

import heapq, time

def scheduler(jobs):
    pq = [(deadline, fn) for fn, deadline in jobs]
    heapq.heapify(pq)
    while pq:
        deadline, fn = pq[0]
        now = time.monotonic()
        if deadline > now:
            time.sleep(deadline - now)
        heapq.heappop(pq)
        fn()

Error Handling¶

Performance Tips¶

• Reach for the standard library first. They are written in C and use bulk O(n) heapify.
• Use heapq.heapreplace (or replace in Java's PQ via poll+offer in a single critical section) instead of pop then push.
• For huge PQs in Python, prefer heapq on a list over queue.PriorityQueue (which adds thread-safe locking overhead).
• Avoid object allocations inside the heap; pre-allocate items if the workload is hot.
• If priorities are small integers, consider a bucket or radix heap — O(1) per op.

Best Practices¶

• Define your comparator once and document the order (min vs max).
• Never mutate an item's priority while it sits in a PQ — wrap push / pop / decrease-key around the field updates.
• Push immutable value objects when possible (record in Java, frozenset/tuple in Python).
• Log the size at periodic checkpoints — runaway growth is the most common PQ bug in production.
• For multi-producer workloads, prefer the language's concurrent PQ rather than building your own lock around a plain heap.

Edge Cases & Pitfalls¶

• Empty PQ: define behaviour of peek/pop up front. Throw, return sentinel, or block.
• Duplicate priorities: ensure stability if your downstream expects FIFO among equals.
• Negative priorities: legal but watch for overflow when subtracting in comparators.
• NaN priorities (floats): NaN breaks total order — guard with assert not isnan(p).
• Mutable payloads: make payload comparison a no-op (tiebreaker counter) so equal priorities never reach the payload.
• Unbounded growth in lazy Dijkstra: an early skip check on pop is what keeps it from exploding.

Common Mistakes¶

1. Confusing the ADT with binary heap: thinking "priority queue" can only mean "binary heap."
2. Forgetting the tiebreaker counter and crashing on equal priorities.
3. Using a max-heap when you wanted min, and vice versa.
4. Mutating a priority while the item is still in the PQ — the invariant rots.
5. Reaching for decrease-key without an indexed structure — there is no way to find the item.
6. Treating peek as pop and not seeing the next item ever change.

Cheat Sheet¶

Visual Animation¶

See animation.html for an interactive view.

The animation demonstrates: - A PQ as the interface — toggle between three backing structures (binary heap, sorted array, BST) and watch the same operations run with different costs. - Stable vs unstable behaviour with the tiebreaker counter. - A bounded PQ in top-k mode evicting items when full.

Summary¶

The priority queue is the ADT you reach for whenever "process the most important thing next" is part of your algorithm. It is almost always backed by a binary heap, but it is good practice to mentally distinguish the interface from the implementation — the two are independent decisions, and different workloads favour different backings.

Further Reading¶

• Introduction to Algorithms (CLRS), Chapter 6.5 — "Priority queues."
• Java — java.util.PriorityQueue and java.util.concurrent.PriorityBlockingQueue Javadoc.
• Go — container/heap package docs.
• Python — heapq module docs, including "Priority Queue Implementation Notes."
• Sedgewick & Wayne, Algorithms, §2.4 — beautifully concise treatment of PQs.