Priority queues

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 — $\Theta(1)$ (it's the root). - EXTRACT-MAX(S) — remove and return that element — $O(\lg n)$. - INSERT(S, x) — add $x$ — $O(\lg n)$. - INCREASE-KEY(S, x, k) — raise $x$'s key to $k \ge$ its current key — $O(\lg 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(\lg 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 \ge$ 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.