Priority Queue — concept (heap-based implementation covered later): Visual walkthrough

This is the visual companion to the Priority Queue concept note. We derive the cost table there, step by step, from zero.

Step 1 — What "priority" even means, as a picture

WHAT. Before any cost, we need to see the object. A priority queue is a bag of items, each carrying a number called its priority. We agree on one rule: lower number = more urgent (a min-priority queue). The rule never changes mid-story.

WHY this convention. We must pin down "most important" as an actual comparable number, otherwise the words "smallest" and "largest" have nothing to bite on. We pick lower-is-more-urgent because it matches the parent's hospital example (triage level 1 = critical).

PICTURE. Four items sit in a box. Each is a pair: a name and a priority tag.

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

Step 2 — The only two moves: insert and extract-min

WHAT. A priority queue promises exactly two actions on that box:

$insert (x, p)$ — drop a new pair into the box.
$extract-min ()$ — remove and return the pair whose $p$ is smallest.

WHY only these. The parent calls a PQ an ADT: it names behaviour, not machinery. Cost lives entirely in how much work each of these two moves takes. So if we can count the work of insert and extract-min for a given storage layout, we have derived everything.

PICTURE. One arrow puts a pair in; one arrow (always pulling the red minimum) takes a pair out.

Step 3 — Layout A: the unsorted list (cheap in, expensive out)

WHAT. Store the pairs in a row, in whatever order they arrive. No tidying.

WHY look here first. It is the laziest possible box. Seeing its costs tells us the price of doing nothing to stay organised.

PICTURE — insert. A new pair just lands at the far right. Nothing else moves.

Because we touch exactly one slot no matter how big the row is, the insert work does not grow with $n$ :

PICTURE — extract-min. Now the pain. To find the red minimum we have no shortcut: we must walk the whole row, comparing every $p$ , remembering the smallest so far.

Step 4 — Layout B: the sorted list (expensive in, cheap out)

WHAT. Keep the row sorted by priority at all times, smallest on the left.

WHY try the opposite. In Layout A the mess was pushed onto extract-min. What if we pay to stay tidy instead? This is the natural "fix" — and watching it fail teaches the real lesson.

PICTURE — extract-min. The red minimum is always the leftmost element. Grab it. Done — no searching.

PICTURE — insert. Here the tidiness bites back. A new pair must slide into its correct slot, and every item to its right must shift over to make room.

Step 5 — Plug the costs in: the $O (n^{2})$ trap

WHAT. Take a realistic workload — an algorithm that does $n$ inserts and $n$ extract-mins (this is exactly what Dijkstra's Algorithm does: push every node, pop every node). Substitute the costs we just derived into the Step 2 formula.

WHY this workload. A single insert or a single extract is meaningless in isolation. Real algorithms hammer both moves many times. Only then does the imbalance turn into a monster.

PICTURE. Two curves. Both naive layouts trace the same steep parabola; something better hugs the floor.

Step 6 — Why balance beats both: the heap idea

WHAT. The escape is a Heap — a layout (built on a Binary Tree, detailed in the next note) that refuses to make either move $O (1)$ but keeps both moves at $O (lo g n)$ .

WHY $lo g n$ and why it wins. $lo g_{2} n$ = how many times you can halve $n$ before reaching 1 — the height of a balanced binary tree. A heap only ever fixes one root-to-leaf path, and that path length is the tree's height. Because $lo g n$ grows agonisingly slowly, balancing both moves crushes the total.

PICTURE. A staircase: $O (1)$ flat, $lo g n$ almost flat, $n$ a steep ramp. The heap lives on the nearly-flat step for both operations.

Step 7 — The degenerate cases (never leave a gap)

WHAT & WHY. A derivation is only trustworthy if the corners hold. We check the sizes where "smallest" gets slippery.

Empty box ( $n = 0$ ). There is no minimum. extract-min and peek must error / return empty, not return garbage. Cost is $O (1)$ everywhere — nothing to search.

One item ( $n = 1$ ). The lone item is the minimum for every layout. All moves are $O (1)$ — the layouts only start to differ once there is a choice of which to remove.

All priorities equal (ties). Every layout still returns some item, but which one is not fixed by the PQ contract. As the parent warns, standard PQs are not stable. If FIFO tie-breaking matters, store the pair $(p, seq)$ where $seq$ is an ever-increasing counter — the smaller $seq$ (earlier insert) then wins ties by the same min-rule.

PICTURE. The three corner boxes side by side: empty (error), single (trivial), all-tied (ambiguous winner, broken by $seq$ ).

The one-picture summary

Everything above collapses into a single frame: two lazy layouts each shove all the cost onto one move (steep $O (n^{2})$ wall), while the heap splits the cost evenly and slips under it ( $O (n lo g n)$ ).

Recall Feynman: retell the whole walkthrough with no symbols

Imagine a box of tickets, each stamped with an urgency number, and a machine that must always hand you the most urgent one. If you never sort the box, throwing a ticket in is instant — but finding the most urgent means squinting at every single ticket, and that gets slower as the box fills. If instead you keep the box perfectly sorted, grabbing the most urgent is instant — but inserting now means elbowing a whole row of tickets aside. Either way, one job stays quick only by making the other job crawl. Now run a real program that both stuffs the box a million times and empties it a million times: the slow job, done a million times, multiplies into a catastrophe — roughly a million-times-a-million pieces of work. The clever fix (a heap, next chapter) refuses to make either job instant. It keeps both jobs at "count how many times you can halve the pile" — a tiny number, about twenty for a million tickets. Twenty is so much smaller than a million that the heap finishes about fifty-thousand times sooner. That's the entire story: don't make one move perfect, make both moves good.

Connections

Priority Queue — concept (parent) — the note this walkthrough visualises.
Heap — the balanced $O (lo g n)$ layout that escapes the trap.
Binary Tree — the shape whose height is that $lo g n$ .
Queue (FIFO) · Stack (LIFO) — the arrival-order disciplines a PQ deliberately breaks.
Dijkstra's Algorithm · Huffman Coding — algorithms that do $n$ inserts and $n$ extracts, so they live or die by this cost.
Abstract Data Type — why "insert / extract-min" is a contract, not code.

Why do both naive PQ layouts hit O(n^2) on n inserts + n extracts?

Each makes one move O(1) only by making the other O(n); that O(n) move, called n times, multiplies to O(n^2).

What does log n represent in the heap's cost?

The height of the balanced binary tree — how many times n can be halved before reaching 1.

For n = 10^6, roughly how much faster is O(n log n) than O(n^2)?

About 50,000× (10^12 vs ~2×10^7).

How do you break ties in FIFO order in a PQ?

Store the pair (p, seq) with an increasing counter seq; smaller seq wins equal priorities.