Priority queues

◈ 4 cards

A max-heap as an ADT: MAXIMUM in Θ(1), INSERT / EXTRACT-MAX / INCREASE-KEY in O(lg n) — the engine of Dijkstra, Prim, and Huffman.

From data structure to abstract type

A max-priority queue maintains a set $S$ of elements keyed by priority and supports four operations:

MAXIMUM(S) — return the element with the largest key — $Θ (1)$ (it's the root).
EXTRACT-MAX(S) — remove and return that element — $O (l g n)$ .
INSERT(S, x) — add $x$ — $O (l g n)$ .
INCREASE-KEY(S, x, k) — raise $x$ 's key to $k \geq$ its current key — $O (l g n)$ .

Backed by a max-heap, all four are cheap because every fix touches only one root-to-leaf (or leaf-to-root) path of length $O (l g n)$ .

Two directions of repair

MAX-HEAPIFY moves a too-small value down. The priority-queue operations also need the opposite. INCREASE-KEY raises a key, which can only violate the property against the parent (the children are still smaller), so it walks up, swapping with the parent while the parent is smaller — exactly insertion sort's inner loop. EXTRACT-MAX saves $A [1]$ , moves the last leaf to the root, shrinks, and MAX-HEAPIFYs down. INSERT is the slick trick: append the new element with key $- \infty$ , then INCREASE-KEY it up to its real key — reusing one routine and guaranteeing the $k \geq$ current-key precondition for any legal $k$ .

Worked example

Insert keys $4, 1, 8, 3, 16, 9, 2$ one at a time (each bubbles up). The root is now $16$ . Extract four times: you get $16, 9, 8, 4$ in that order, each extract sifting the moved leaf back down. MAXIMUM then returns $3$ — the largest of the three survivors ${3, 2, 1}$ . The runnable exercise reproduces exactly this transcript.

This ADT is the workhorse of later modules: Dijkstra and Prim use a min-priority queue with DECREASE-KEY; Huffman repeatedly EXTRACT-MINs the two lightest nodes.

MAXIMUM only reads the root, so it is free. The other three each fix a single path of length ⌊lg n⌋ — which is the whole reason a heap backs this ADT.

INSERT in the worked transcript (0-indexed, as in the runnable exercise). The new key is appended, then walks *up* — MAX-HEAPIFY only walks down, which is why it cannot do this repair.