Priority Queues

CS205 Data Structures

Use arrow keys or buttons to navigate

What is a Priority Queue?

A collection where each element has a priority. The element with the highest priority (lowest key) is served first.

Interactive: Queue vs Priority Queue

Analogy: Hospital ER Triage

Patients are NOT seen in arrival order. The most critical case (lowest priority number) is treated first.

Key Idea

A priority queue is an ADT that supports inserting elements with keys and removing the element whose key is minimal (or maximal). Not FIFO!

The Priority Queue ADT

A PQ stores entries — each is a (key, value) pair.

Core Operations

Method	Description
`insert(k, v)`	Insert entry with key k, value v
`removeMin()`	Remove & return min-key entry
`min()`	Return (don't remove) min-key entry
`size()`	Number of entries
`isEmpty()`	Is PQ empty?

Warning

removeMin() and min() throw an error if called on an empty PQ. Always check isEmpty() first.

Interactive Trace

Keys and Comparators

Keys define priority. But how do we compare them?

Total Order Relations

A valid comparison rule must satisfy:

Reflexive: k ≤ k
Antisymmetric: if k₁ ≤ k₂ and k₂ ≤ k₁, then k₁ = k₂
Transitive: if k₁ ≤ k₂ and k₂ ≤ k₃, then k₁ ≤ k₃

The Comparator Pattern

interface Comparator<K> {
    int compare(K a, K b);
    // negative → a < b
    // zero    → a == b
    // positive → a > b
}

Analogy

A comparator is like a judge at a competition — swap in a different judge to rank contestants by a different criterion.

Interactive: Try Different Comparators

Compare by:

Key Idea

Any two keys must be comparable — this makes it a total order. The comparator pattern lets you swap ordering strategies without changing the PQ.

Implementation 1: Unsorted List

Insert fast, but finding the minimum requires scanning everything.

Interactive Unsorted List PQ

Complexity

Operation	Time
`insert`	O(1)
`removeMin`	O(n)
`min`	O(n)
`size`, `isEmpty`	O(1)

Key Idea

Insert is O(1) — just append to the end. But removeMin is O(n) because we must scan every entry to find the smallest key.

When to Use

Good for insert-heavy workloads with rare removes. Terrible if you remove frequently.

Implementation 2: Sorted List

Keep entries sorted by key. Min is always at the front, but insertion requires walking.

Interactive Sorted List PQ

Complexity

Operation	Time
`insert`	O(n)
`removeMin`	O(1)
`min`	O(1)
`size`, `isEmpty`	O(1)

Key Idea

removeMin is O(1) — the smallest is always at front. But insert is O(n) — we walk the list to find the correct sorted position.

When to Use

Good for remove-heavy workloads with rare inserts. Terrible if you insert frequently.

Unsorted vs Sorted: Side by Side

Neither list approach gives us the best of both worlds.

Operation	Unsorted	Sorted
`insert(k,v)`	O(1)	O(n)
`removeMin()`	O(n)	O(1)
`min()`	O(n)	O(1)

Analogy

Unsorted list = throwing clothes into a pile. Fast to add, slow to find what you need.

Sorted list = keeping a perfectly organized closet. Slow to put away, fast to grab the right item.

Can We Do Better?

What if both insert and removeMin were O(log n)?

PQ-Sort: Selection Sort

Use an unsorted list PQ to sort — this is Selection Sort!

Step-Through Animation

How It Works

Phase 1: Insert all n elements — each O(1)
Phase 2: Call removeMin() n times — scans n, n-1, ... 1

// Phase 1: insert all — O(n)
for (E elem : input)
    pq.insert(elem, elem);
 
// Phase 2: removeMin n times — O(n²)
for (int i = 0; i < n; i++)
    output[i] = pq.removeMin().getValue();

Complexity

Phase 1: n × O(1) = O(n)
Phase 2: n + (n-1) + ... + 1 = n(n+1)/2 = O(n²)
Total: O(n²)

Why "Selection" Sort?

Each removeMin selects the minimum from the remaining unsorted elements — exactly what Selection Sort does!

PQ-Sort: Insertion Sort

Use a sorted list PQ to sort — this is Insertion Sort!

Step-Through Animation

How It Works

Phase 1: Insert all n elements — each walks the sorted list to find position
Phase 2: Call removeMin() n times — each is O(1) from front

// Phase 1: insert into sorted PQ — O(n²)
for (E elem : input)
    pq.insert(elem, elem); // walks to pos
 
// Phase 2: removeMin n times — O(n)
for (int i = 0; i < n; i++)
    output[i] = pq.removeMin().getValue();

Complexity

Phase 1: 1 + 2 + ... + n = n(n+1)/2 = O(n²)
Phase 2: n × O(1) = O(n)
Total: O(n²)

Why "Insertion" Sort?

Like sorting playing cards: pick up each card and slide it into the right spot among cards you're already holding.

Can We Do Better?

Both PQ-based sorts are O(n²). Is there a middle ground?

The Big Insight

The binary heap achieves O(log n) for both insert and removeMin by using a complete binary tree with the heap-order property.

How Does It Work?

// Heap-order property:
// Every node's key ≤ its children's keys
// → min is always at the ROOT
 
insert:     add at bottom, BUBBLE UP
            → O(log n) swaps max
 
removeMin:  remove root, move last to top
            TRICKLE DOWN
            → O(log n) swaps max
 
PQ-Sort:    n × O(log n) = O(n log n)
            = HEAP SORT!

Analogy

The heap is like a corporate hierarchy: the CEO (min key) is always at the top. Promoting someone (insert) bubbles them up through levels. Firing the CEO (removeMin) promotes from below.

Full heap details → next lecture!

The Entry / Key-Value Pattern

PQs store entries, not bare keys. Each entry is a (key, value) pair.

Why Separate Key from Value?

The key determines priority (ordering)
The value is the actual data you care about
Same value might need different priorities in different contexts

interface Entry<K, V> {
    K getKey();     // the priority
    V getValue();   // the payload
}

Analogy: Boarding Pass

The key = boarding group number. The value = you (the passenger). The airline decides your priority, not your name.

Examples Across Domains

Key Idea

Entries decouple "what you store" from "how it's prioritized." This makes the PQ reusable across many domains.

Adaptable Priority Queue

Sometimes you need to change a key or remove an arbitrary entry — not just the minimum.

Additional Operations

Method	Description
`remove(e)`	Remove entry e
`replaceKey(e, k)`	Change key of e to k
`replaceValue(e, v)`	Change value of e

Location-Aware Entries

Interactive: Dijkstra Scenario

Key Idea

An adaptable PQ lets you modify entries already in the queue. Essential for graph algorithms like Dijkstra's and Prim's.

Application: Job Scheduling

Operating systems use priority queues to decide which process runs next.

Interactive OS Scheduler

How the PQ Helps

CPU always runs the highest-priority (lowest key) process
New processes arrive via insert(priority, process)
Scheduler calls removeMin() to pick the next process
With a heap: O(log n) per operation — handles thousands of processes

Analogy

Like a hospital with one doctor: the most critical patient always gets treated next, but new patients arrive at any time and get triaged into the queue.

Key Idea

The PQ ensures that system-critical tasks (interrupts, real-time processes) always preempt lower-priority work like background backups.

Application: Event-Driven Simulation

Simulate a system by processing events in chronological order.

Interactive Bank Simulation

How It Works

// key = event time, value = event
PQ<Event> pq = new PQ<>();
pq.insert(0, "Bank opens");
 
while (!pq.isEmpty()) {
    Event e = pq.removeMin();
    clock = e.time;
    process(e);
    // processing may INSERT new
    // future events into the PQ
}

Key Idea

Events are entries with time as the key. Processing an event often creates new future events. The PQ always gives us the chronologically next event — no need to iterate through all possibilities.

Analogy

Like a director with a schedule of scenes to film. Each scene might add new scenes. The PQ picks the one that happens earliest in the story timeline.

Application: Dijkstra's Algorithm Preview

The priority queue is the engine behind the famous shortest-path algorithm.

Interactive Graph Trace

Click Step to begin

The Algorithm

PQ = { (0, source) }
dist[source] = 0, all others = ∞
 
while PQ not empty:
    (d, u) = PQ.removeMin()
    for each neighbor v of u:
        if d + weight(u,v) < dist[v]:
            dist[v] = d + weight(u,v)
            PQ.insert(dist[v], v)

Key Idea

Dijkstra "greedily" picks the unvisited vertex with the smallest known distance using removeMin(). With a heap-based PQ, the algorithm runs in O((V + E) log V).

Why PQ Matters Here

Without a PQ, finding the next closest vertex costs O(V) per step → O(V²) total. With a heap PQ, each step is O(log V) — a huge speedup on large graphs.

Full details in the Graph Algorithms unit.

Challenge: Trace the PQ

What does removeMin() return after this sequence?

PQ pq = new PQ();  // min-heap
pq.insert(8, "X");
pq.insert(3, "Y");
pq.insert(5, "Z");
pq.insert(1, "W");
pq.removeMin();  // first remove
pq.insert(2, "V");
pq.insert(7, "U");
pq.removeMin();  // second remove
pq.removeMin();  // ← WHAT IS THIS?

What entry does the third removeMin() return?

(3, "Y") (5, "Z") (2, "V") (7, "U")

Step-Through Helper

Application: Huffman Coding Preview

Build optimal prefix-free codes for data compression using a priority queue.

Interactive Huffman Build

The Algorithm

Insert each character as a leaf node into PQ (key = frequency)
While PQ has more than one entry:
- T1 = PQ.removeMin()
- T2 = PQ.removeMin()
- Merge into new node (freq = T1 + T2)
- PQ.insert(merged node)
Last entry = Huffman tree root

Key Idea

The PQ always merges the two least frequent nodes. This greedy strategy produces an optimal prefix code. Two removeMin + one insert per step.

Why It Works

Rare characters get long codes (deep in tree), frequent characters get short codes (near root). Total bit usage is minimized.

Challenge: Fix the PQ Sort

This PQ-based sort has a bug — find and fix it

// Sort using an unsorted-list PQ
public static void pqSort(int[] arr) {
    PQ pq = new UnsortedListPQ();
    for (int x : arr)
        pq.insert(x, x);
    
    for (int i = 0; i < arr.length; i++)
        arr[i] = pq.removeMin().getValue();
}

Wait — this code looks correct. But what if we change the PQ to a max-heap (removeMax instead of removeMin)?

// Using a MAX-heap PQ — has a bug!
public static void pqSort(int[] arr) {
    MaxPQ pq = new MaxHeapPQ();
    for (int x : arr)
        pq.insert(x, x);
    
    for (int i = 0; i < arr.length; i++)
        arr[i] = pq.removeMax().getValue();
}

What's wrong and how do you fix it?

Implementation Comparison

How do all PQ implementations stack up?

Choose your implementation:

Unsorted List — few removes, many inserts, small n

Sorted List — few inserts, many removes, small n

Binary Heap — general purpose PQ — best default

Balanced BST — need ordered iteration or range queries too

Key Idea

The binary heap is the sweet spot: O(log n) insert and removeMin, O(1) min, simple array-based storage, and it gives us Heap Sort at O(n log n).

BST vs Heap

A balanced BST (AVL, Red-Black) also achieves O(log n) for everything, but has higher constant factors and more complex implementation. Heaps are preferred when you only need PQ operations.

Sorting Connection Summary

Challenge: Pick the Right PQ

Match each scenario to the best PQ implementation

Summary & Cheat Sheet

Everything on one slide

Core Concepts

Priority Queue = smallest (or largest) key removed first
Entry = (key, value) pair; key determines priority
Comparator = defines the total order on keys
Adaptable PQ = supports remove(e), replaceKey(e, k)

Sorting Connection

Applications

OS Job / Process Scheduling
Event-Driven Simulation
Dijkstra's Shortest Path
Huffman Coding (compression)
Prim's MST, A* Search

Complexity Cheat Sheet

	Unsorted	Sorted	Heap
`insert`	O(1)	O(n)	O(log n)
`removeMin`	O(n)	O(1)	O(log n)
`min`	O(n)	O(1)	O(1)

Key Takeaways

PQ ≠ Queue — it's not FIFO!
Keys define priority; entries = (key, value)
Unsorted list → fast insert, slow remove
Sorted list → fast remove, slow insert
Heap → fast BOTH! The gold standard
PQ-Sort with heap = O(n log n) = Heap Sort

Next up: Binary Heaps — the data structure that makes PQs efficient.

Quiz: Priority Queues

Test your understanding — 3 questions

Q1: Which PQ implementation gives O(n²) Selection Sort?

Sorted list — removeMin walks the list Unsorted list — removeMin scans for minimum Binary heap — removeMin is O(log n) Balanced BST — removeMin is O(log n)

Q2: Why does an adaptable PQ need location-aware entries?

To store larger values To find an entry in O(1) instead of O(n) when changing its key To support FIFO ordering as a fallback To allow duplicate keys

Q3: What makes a binary heap better than both list-based PQ implementations?

It uses less memory It achieves O(log n) for both insert and removeMin It supports random access by index It maintains a sorted order at all times

Quiz: Selection vs Insertion Sort

Identify which PQ-sort each animation represents

Sort A

Selection Sort (unsorted list PQ) Insertion Sort (sorted list PQ)

Sort B

Selection Sort (unsorted list PQ) Insertion Sort (sorted list PQ)

Quiz: Predict the Output

What prints at the end?

PQ pq = new MinHeapPQ();
int[] data = {6, 1, 8, 3, 5, 2};
 
for (int x : data)
    pq.insert(x, "v"+x);
 
String result = "";
while (pq.size() > 2) {
    Entry e = pq.removeMin();
    result += e.getKey() + " ";
}
System.out.println(result);
System.out.println(pq.min().getKey());

What are the two lines of output?

Line 1 (result):

Line 2 (min key):