Priority Queue — concept (heap-based implementation covered later): Worked examples

This page is the "no surprises" drill for the Priority Queue concept note. We take every kind of situation a priority queue can throw at you and work one example through each — slowly, from zero, guessing the answer before we compute it.

The scenario matrix

Read each row as "a kind of situation you must never be surprised by."

#	Case class	Concrete twist	Covered by
1	Min-PQ, distinct priorities	ordinary extract order	Example 1
2	Max-PQ via negation	want largest out first, only min-PQ available	Example 2
3	Ties (equal priorities)	stable vs unstable removal	Example 3
4	Negative & mixed-sign priorities	zero and negatives together	Example 4
5	Degenerate inputs	empty PQ, single element, all-equal	Example 5
6	Size-capped PQ (top-K)	keep only K best from a stream	Example 6
7	Real-world word problem	ER triage over time, insert & extract interleaved	Example 7
8	Cost / limiting behaviour	why $O (n^{2})$ vs $O (n lo g n)$ actually matters	Example 8
9	Exam twist	compound key $(p, seq)$ to force FIFO ties	Example 9

Before any of this, one picture of the behaviour we are testing — the top always leaves first.

Figure — Priority Queue — concept (heap-based implementation covered later)

Read the figure (Figure s01 — min-PQ output belt): on the left are the four elements as they sit inside the PQ — labelled boxes A:5, B:2, C:8, D:4, drawn in their insert order A, B, C, D to stress that this order is irrelevant to what leaves. The green arrow shows the very first extract-min reaching past A into the set and grabbing the smallest priority, B:2. On the right is the output belt, a vertical stack that fills top-to-bottom in ascending priority ( $2, 4, 5, 8$ ) as the time arrow flows downward. The single idea the figure teaches: repeated min-removal turns any jumble of priorities into a sorted output stream — and that belt is exactly what we now stress-test, case by case.

Example 1 — Min-PQ, all distinct (Case 1)

Worked example Statement

Start empty. Do: insert(A,5), insert(B,2), insert(C,8), insert(D,4). Then extract-min four times. What sequence comes out?

Forecast: cover the right column and guess the order before reading on.

Steps

After the four inserts the PQ holds ${A : 5, B : 2, C : 8, D : 4}$ . Why this step? Insertion order does not decide output; we just record who is present with what priority.
First extract-min: smallest priority is $2$ → B leaves. Why this step? A min-PQ's one promise is "return the current smallest priority."
Remaining ${A : 5, C : 8, D : 4}$ . Smallest is $4$ → D leaves. Why this step? extract-min re-runs on the reduced set each call; with B gone, $4$ is now the smallest remaining priority.
Remaining ${A : 5, C : 8}$ . Smallest is $5$ → A leaves. Why this step? Same rule again on the shrunken set — $5 < 8$ , so A precedes C.
Remaining ${C : 8}$ → C leaves. Why this step? One element left, so it is trivially the minimum and exits last.

Answer: B, D, A, C (priorities $2, 4, 5, 8$ ).

Verify: the emitted priority sequence $2, 4, 5, 8$ is sorted ascending — that is the definition of "min first, repeatedly," so it must come out sorted. ✅

Example 2 — Max-PQ from a min-PQ by negation (Case 2)

Worked example Statement

You have only a min-PQ, but you want the largest value out first. Values: $40, 10, 70, 25$ .

Forecast: what do you store, and what leaves first?

Steps

Store each value $p$ as $- p$ : insert $- 40, - 10, - 70, - 25$ . Why this step? A min-PQ hands back the smallest number. The most negative number corresponds to the largest original value, so negating flips "largest" into "smallest."
extract-min returns $- 70$ (most negative). Why this step? Among $- 40, - 10, - 70, - 25$ the minimum is $- 70$ .
Negate back: $- (- 70) = 70$ . That is the true maximum. Why this step? We stored negatives, so we must undo the flip to report the real value the user cares about.
Continue: next min is $- 40 \Rightarrow 40$ , then $- 25 \Rightarrow 25$ , then $- 10 \Rightarrow 10$ . Why this step? Each later extract-min again pulls the most-negative remaining stored key, i.e. the largest remaining original value.

Answer: out order $70, 40, 25, 10$ (largest first).

Verify: $70, 40, 25, 10$ is the input sorted descending — exactly max-PQ behaviour. And $- (- 70) = 70$ recovers the original. ✅

Example 3 — Ties: is a PQ stable? (Case 3)

Worked example Statement

Min-PQ. Insert three tasks all with priority 5, in this order: X, Y, Z. extract-min three times. In what order do they come out?

Forecast: is it guaranteed X, Y, Z?

Steps

All three share priority $5$ , so "smallest priority" does not single anybody out. Why this step? The PQ's contract only orders by priority. When priorities tie, the contract is silent.
A standard PQ (and a binary Heap) is not stable: the tie-break order is implementation-defined. It might be X,Y,Z, or Z,X,Y, or anything. Why this step? Nothing in the extract rule reads insertion time, so it can't promise FIFO among equals.
To force insertion order, attach a sequence counter (see Example 9). Why this step? Since priority alone can't separate ties, we need an extra distinguishing field to make removal deterministic.

Answer: Not guaranteed to be X, Y, Z. Any permutation of the tied set is contract-valid.

Verify: the only guarantee is that all three priority- $5$ items leave before any priority- $> 5$ item and after any priority- $< 5$ item. Their internal order is undefined. ✅ (This matches the parent note's "PQs are not stable.")

Example 4 — Negative and mixed-sign priorities, including zero (Case 4)

Worked example Statement

Min-PQ. Insert priorities: $3, - 2, 0, - 5, 4$ . extract-min until empty.

Forecast: where do $0$ and the negatives land?

Steps

Collect: ${3, - 2, 0, - 5, 4}$ . Why this step? "Smaller" follows ordinary number-line order — negatives are smaller than $0$ , which is smaller than positives.
Smallest is $- 5$ → out. Why this step? On the number line, $- 5$ sits furthest left.
Then $- 2$ → out. Why this step? With $- 5$ removed, the leftmost remaining value on the number line is $- 2$ .
Then $0$ → out. Why this step? Both negatives are gone; $0$ is now the smallest remaining, still left of the positives.
Then $3$ , then $4$ . Why this step? Only positives remain; the smaller positive $3$ precedes $4$ .

Answer: out order $- 5, - 2, 0, 3, 4$ .

Verify: result is the multiset sorted ascending; every negative precedes $0$ , which precedes every positive. No sign is treated specially — a priority is just a real number. ✅

Example 5 — Degenerate inputs: empty, single, all-equal (Case 5)

Worked example Statement

Handle three edge PQs: (a) empty PQ — call peek and extract-min; (b) PQ with one element insert(A,7) — then extract-min; (c) PQ with insert(A,7), insert(B,7), insert(C,7) — then extract-min once.

Forecast: which of these can error, and which are perfectly well-defined?

Steps

(a) Empty. peek/extract-min on an empty PQ is undefined — there is no top. Implementations either return a sentinel (None/null), throw an exception, or (in C++) are undefined behaviour if you don't check empty() first. Why this step? The contract "return the smallest" needs at least one element to talk about.
(b) Single element. Smallest of a one-element set is that element → A leaves; PQ becomes empty. Why this step? With one candidate there is nothing to compare; it is trivially the minimum.
(c) All-equal ( $7, 7, 7$ ). extract-min returns some priority- $7$ element (which one is unstable, see Example 3); size drops to $2$ . Why this step? Every element ties for smallest; exactly one is removed per call.

Answer: (a) error / sentinel — must guard with an emptiness check; (b) returns A; (c) returns one of A/B/C (unspecified which).

Verify: min of a set of size $\geq 1$ is well-defined; min of the empty set is not — this is why every safe PQ use pattern is while not pq.empty(): x = pq.extract(). ✅

Example 6 — Size-capped PQ: top-K from a stream (Case 6)

Worked example Statement

Keep the 3 largest values from the stream $8, 3, 12, 1, 15, 6$ using a min-PQ of size ≤ 3.

Forecast: which three survive, and why is the small one the one we throw away?

Steps — the rule: after each insert, if size $> 3$ , extract-min (drop the current smallest of the kept set).

insert 8 → ${8}$ Why this step? Below the cap of 3, so we simply add and drop nothing — every early value is provisionally a "survivor" until proven weakest.
insert 3 → ${3, 8}$ Why this step? Still below the cap, so 3 joins without eviction; we never discard while there is room.
insert 12 → ${3, 8, 12}$ (size 3, OK) Why this step? Exactly at the cap of 3 — no eviction is triggered because size did not exceed 3.
insert 1 → ${1, 3, 8, 12}$ , size 4 → extract-min drops 1 → ${3, 8, 12}$ Why this step? For "top-K largest," the kept set's smallest is the weakest survivor, so a min-PQ's extract-min removes exactly the right one.
insert 15 → ${3, 8, 12, 15}$ , size 4 → drop 3 → ${8, 12, 15}$ Why this step? Same rule again: after adding 15 the new weakest survivor is 3, so it is evicted.
insert 6 → ${6, 8, 12, 15}$ , size 4 → drop 6 → ${8, 12, 15}$ Why this step? 6 is smaller than everything already kept, so it becomes the min and is immediately dropped — a value can be inserted and evicted on the same step.

Answer: top-3 = ${8, 12, 15}$ .

Verify: brute force — sort the stream: $1, 3, 6, 8, 12, 15$ ; the three largest are $8, 12, 15$ . Match. Memory used never exceeded $K + 1 = 4$ elements, not the whole stream. ✅

Example 7 — Real-world word problem: ER triage over time (Case 7)

Worked example Statement

An emergency room uses a min-PQ (smaller number = more urgent). Events happen in this timeline; a treat means "extract the most urgent patient now present."

arrive(Ann,5), arrive(Bob,2), treat, arrive(Cal,1), arrive(Dee,4), treat, treat.

Forecast: who gets treated on each treat, and does anyone "cut the line"?

Steps

After arrive(Ann,5), arrive(Bob,2): present ${A nn : 5, B o b : 2}$ . Why this step? We must record the current waiting-room state before any treat, because extract-min acts on exactly who is present at that instant — not on future arrivals.
treat → smallest priority $2$ → Bob treated. Present ${A nn : 5}$ . Why this step? Bob arrived second but is more urgent — priority beats arrival, the whole point of a PQ.
arrive(Cal,1), arrive(Dee,4): present ${A nn : 5, C a l : 1, D ee : 4}$ . Why this step? New arrivals join the remaining set (Ann is still waiting); we re-record the state so the next treat sees the freshly-updated waiting room including the urgent Cal.
treat → smallest is $1$ → Cal. Present ${A nn : 5, D ee : 4}$ . Why this step? Cal just walked in but is the most urgent (heart attack), so she jumps ahead of Ann who was waiting.
treat → smallest is $4$ → Dee. Present ${A nn : 5}$ . Why this step? Of the two remaining, Dee's $4$ beats Ann's $5$ ; extract-min again returns the minimum of the current set.

Answer: treated order = Bob, Cal, Dee (priorities $2, 1, 4$ ). Ann (priority 5) still waits despite arriving first.

Verify: the emitted priorities are $2, 1, 4$ — not sorted overall, because inserts happen between extracts. Each individual treat still returned the minimum of whoever was present at that moment ( $2$ of ${5, 2}$ ; $1$ of ${5, 1, 4}$ ; $4$ of ${5, 4}$ ). ✅

Example 8 — Limiting behaviour: why the balance matters (Case 8)

Worked example Statement

A workload does $n$ inserts followed by $n$ extract-mins, with $n = 1, 000, 000$ . Estimate the total work for an unsorted list vs a binary Heap, and the speedup factor. (Reminder: $O (n^{2})$ means work grows with the square of $n$ ; $O (n lo g n)$ grows only a hair faster than $n$ itself — see the Big-O reminder at the top.)

Forecast: guess the ratio — is it 10×, 1000×, or more?

Steps

Unsorted list: insert is $O (1)$ , extract-min is $O (n)$ (scan all). Total $\approx n \cdot 1 + n \cdot n = n + n^{2} \approx n^{2}$ . Why this step? The dominant term for large $n$ is $n^{2}$ ; the $n$ from inserts is negligible.
Plug $n = 1 0^{6}$ : $n^{2} = 1 0^{12}$ "steps." Why this step? Substituting the concrete size turns the growth rate into a number we can compare.
Heap: both ops are $O (lo g_{2} n)$ . Total $\approx 2 n lo g_{2} n$ . Why this step? $2 n$ operations ( $n$ inserts $+$ $n$ extracts), each costing about $lo g_{2} n$ .
Plug in: $lo g_{2} (1 0^{6}) \approx 19.93$ , so $2 \cdot 1 0^{6} \cdot 19.93 \approx 3.99 \times 1 0^{7}$ . Why this step? Same substitution, this time into the heap's growth formula.
Speedup $= \frac{1 0 ^{12}}{3.99 \times 1 0 ^{7}} \approx 2.5 \times 1 0^{4}$ . Why this step? Dividing the two totals converts "which is bigger" into "how many times bigger."

Answer: unsorted $\approx 1 0^{12}$ ; heap $\approx 4 \times 1 0^{7}$ ; heap is roughly 25,000× faster.

Verify: order-of-magnitude check — $1 0^{12} / (4 \times 1 0^{7}) = 2.5 \times 1 0^{4}$ . This is why the concept note calls the heap the practical winner: neither naive list balances both operations. ✅

The figure below plots both growth curves on a log–log grid so you can see the gap open up.

Read the figure (Figure s02 — cost growth curves): the horizontal axis is $n$ (number of elements) and the vertical axis is total steps, both on log scales so that power-law curves appear as straight lines. The red curve is the unsorted list's $n^{2}$ cost; the green curve is the heap's $2 n lo g_{2} n$ cost. The red line is visibly steeper, so it climbs far faster. Two dots mark $n = 1 0^{6}$ : red sits at $\approx 1 0^{12}$ , green at $\approx 4 \times 1 0^{7}$ , and the yellow annotation points at the roughly $25, 000 \times$ vertical gap between them. The one idea: the two curves never cross back — the heap's advantage only widens as $n$ grows, which is the entire justification for learning heaps next.

Example 9 — Exam twist: force FIFO on ties with a compound key (Case 9)

Worked example Statement

You must make a min-PQ break ties in insertion order (stable). Tasks arrive: T1(p=5), T2(p=5), T3(p=2), T4(p=5). Use the key $(p, seq)$ where seq is a counter $0, 1, 2, \dots$ increasing with each insert. Give the extract order.

Forecast: among the three priority-5 tasks, which leaves first?

Steps

Attach a seq at insertion time: $T 1 \to (5, 0)$ , $T 2 \to (5, 1)$ , $T 3 \to (2, 2)$ , $T 4 \to (5, 3)$ . Why this step? The PQ compares pairs lexicographically (see the definition above): first by $p$ , and only if $p$ ties, by seq. Since seq is unique and increasing, ties now resolve to "earliest inserted first."
Smallest pair: compare first components. $T 3$ has $p = 2$ , the smallest → $(2, 2)$ out first → T3. Why this step? $2 < 5$ , so seq never even needs to be looked at here.
Remaining $(5, 0), (5, 1), (5, 3)$ all tie on $p = 5$ ; compare seq: smallest is $0$ → T1. Why this step? With the left entries equal, lexicographic order falls through to the right entry, and $0$ is the smallest seq.
Then seq $1$ → T2, then seq $3$ → T4. Why this step? Same tie-break continues among the still-equal priorities; ascending seq reproduces insertion order.

Answer: extract order = T3, T1, T2, T4.

Verify: T3 (urgent, $p = 2$ ) leaves first; the three $p = 5$ tasks leave in their insertion order $T 1, T 2, T 4$ — exactly the FIFO tie-break the counter was designed to enforce. Lexicographic pairs sorted: $(2, 2) < (5, 0) < (5, 1) < (5, 3)$ . ✅ (This is the parent note's "P for priority, S for sequence" mnemonic in action.)

Active Recall

Recall Q: In Example 7, why is the emitted priority sequence

$2, 1, 4$ not sorted? Because inserts happen between extracts. Each treat returns the min of whoever is present at that moment, not the global min of all patients ever.

Recall Q: For "top-K largest," why do we use a

min-PQ and drop its minimum? The kept set's smallest is the weakest survivor. extract-min removes exactly that when size exceeds K, so the K largest remain — in only $O (K)$ memory.

Recall Q: What must you always check before

extract-min? That the PQ is non-empty. Extracting from an empty PQ is undefined (error / sentinel).

Connections

Parent concept note
Heap — makes both insert and extract $O (lo g n)$ ; Example 8's fast column.
Binary Tree — the shape a heap secretly is.
Queue (FIFO) — the stable, arrival-ordered contrast to Example 3/9.
Stack (LIFO) — the other ordering discipline.
Dijkstra's Algorithm — the interleaved insert/extract of Example 7 at scale.
Huffman Coding — repeatedly extract two minima.
Abstract Data Type — PQ promises behaviour, not implementation.