Priority Queues

A priority queue is an abstract data type storing a dynamic collection of elements, each associated with a key (its priority), and supporting at least three operations: `Insert(x)`, which adds element `x`; `ExtractMin()` (or `ExtractMax()`), which removes and returns the element with the smallest (or largest) key; and often `DecreaseKey(x, newKey)`, which lowers `x`'s key in place, re-establishing order. A related read-only operation, `FindMin()`, returns the minimum without removing it. Ties in priority may be broken arbitrarily or by insertion order (making the structure stable), depending on the application. The ADT deliberately says nothing about how these operations are implemented — only their signatures and guarantees. This separation matters because several structures realize the interface with different tradeoffs: sorted arrays give O(1) extract-min but O(n) insert; unsorted arrays give O(1) insert but O(n) extract-min; balanced binary search trees give O(log n) for everything but with larger constants and more memory overhead; and the binary heap gives O(log n) insert and extract-min with excellent constants and O(1) extra space, at the cost of O(n) arbitrary search unless auxiliary bookkeeping is added. This article focuses on the binary heap as the canonical implementation, since it is the one used almost universally in practice for graph algorithms and schedulers. The key structural idea reused from Binary Heaps is the heap-order property: in a min-heap, every node's key is less than or equal to the keys of its children, which forces the global minimum to sit at the root. Combined with the shape property — the tree is complete, filled left to right at every level except possibly the last — this lets the heap be stored implicitly in a plain array with no pointers, using arithmetic to locate parents and children. The priority-queue ADT adds one further requirement beyond the plain heap: to support `DecreaseKey` in O(log n), the structure must be able to locate an arbitrary element's current array position instantly, which is why practical priority-queue implementations pair the heap array with a handle or index map from element identity to array index.

A binary min-heap stores `n` elements in an array `A[1..n]` (1-indexed for clean arithmetic). For index `i`: ``` parent(i) = floor(i / 2) left(i) = 2i right(i) = 2i + 1 ```

Insert(x). Append `x` at position `n+1` (the next open slot in the complete tree), then repeatedly compare it to its parent and swap upward while it is smaller — this is called sift-up or bubble-up. The process terminates when `x` reaches the root or finds a parent no larger than itself.

ExtractMin(). The minimum is always `A[1]`. Remove it, move the last element `A[n]` into position 1, shrink the array by one, and restore heap order by sift-down (bubble-down): repeatedly swap the node with its smaller child until it is smaller than both children or has none.

DecreaseKey(x, newKey). Given the array index of `x` (found via an index map), lower its key and sift it up — decreasing a key can only violate the heap property with respect to its ancestors, never its descendants, so only sift-up is needed.

IncreaseKey / arbitrary update / Delete(x) follow symmetrically: increasing a key requires sift-down; deleting an arbitrary element is done by decreasing its key to −∞ (conceptually) and extracting it, or directly by replacing it with the last element and sifting in whichever direction restores order. ``` function BUILD-INDEX-MAP(A): // pos[x] = current array index of element x for i in 1..length(A): pos[A[i].id] = i function SWAP(A, pos, i, j): swap(A[i], A[j]) pos[A[i].id] = i pos[A[j].id] = j function SIFT-UP(A, pos, i): while i > 1 and A[parent(i)].key > A[i].key: SWAP(A, pos, i, parent(i)) i = parent(i) function SIFT-DOWN(A, pos, i, n): while true: l = 2i r = 2i + 1 smallest = i if l <= n and A[l].key < A[smallest].key: smallest = l if r <= n and A[r].key < A[smallest].key: smallest = r if smallest == i: break SWAP(A, pos, i, smallest) i = smallest function INSERT(A, pos, n, x): n = n + 1 A[n] = x pos[x.id] = n SIFT-UP(A, pos, n) return n function EXTRACT-MIN(A, pos, n): if n == 0: error "heap is empty" min = A[1] A[1] = A[n] pos[A[1].id] = 1 n = n - 1 if n > 0: SIFT-DOWN(A, pos, 1, n) delete pos[min.id] return min, n function DECREASE-KEY(A, pos, x_id, newKey): i = pos[x_id] if newKey > A[i].key: error "new key is larger than current key" A[i].key = newKey SIFT-UP(A, pos, i) ``` Each `SIFT-UP` or `SIFT-DOWN` call moves an element along a single root-to-leaf path, and the tree's height is `⌊log₂ n⌋` because it is complete — this is the single fact from which every complexity bound below follows.

Time complexity. `Insert`, `ExtractMin`, and `DecreaseKey` each run in `O(log n)` time, and `FindMin` runs in `O(1)` time. Justification. The heap's shape invariant forces the tree to be complete, so with `n` elements its height is exactly `⌊log₂ n⌋`. Both `SIFT-UP` and `SIFT-DOWN` move an element along a single path from a leaf toward the root, or from the root toward a leaf, doing `O(1)` work (one comparison-and-possible-swap) per level. Hence each call performs at most `O(log n)` swaps. `Insert` does one append (`O(1)`) plus one sift-up (`O(log n)`). `ExtractMin` does one removal and one sift-down (`O(log n)`). `DecreaseKey` looks up the position via the index map in `O(1)` (a hash table or array keyed by element id) and then sifts up in `O(log n)`. `FindMin` simply reads `A[1]`.

Space complexity. `O(n)` for the array plus `O(n)` for the index map — both linear, with small constants, and no pointer overhead per node, unlike pointer-based trees.

Correctness — heap-order invariant. Define the invariant H(i): for every node `i` in the array with a parent, `A[parent(i)].key ≤ A[i].key`. We argue each operation preserves `H` for all indices, by induction on the number of operations performed.

• Base case: the empty heap trivially satisfies `H`.
• Insert: appending `x` at position `n+1` may only violate `H` at the single edge `(parent(n+1), n+1)`, since no other parent-child relationship changed. `SIFT-UP` repeatedly checks exactly this edge, and if violated, swaps — which fixes that edge and shifts the potential violation one level up, to `(parent(new position), new position)`. The loop terminates when either the root is reached or the edge holds, at which point every edge in the tree satisfies `H` again.
• ExtractMin: removing `A[1]` and promoting the former last element `A[n]` to the root can only violate `H` at edges from the root downward — every other edge is untouched. `SIFT-DOWN` repeatedly checks the two child edges of the current node, swaps with the smaller violating child if any violation exists, and recurses into that child's position. Choosing the smaller child (not just any child) is essential: swapping with the larger child could leave the other child smaller than the new parent, reintroducing a violation. The loop terminates at a leaf or when both child edges hold.
• DecreaseKey: lowering `A[i].key` can only violate `H` on the edge `(parent(i), i)`, since children's keys are unaffected and still ≥ the (now smaller) `A[i].key`. `SIFT-UP` handles this exactly as in `Insert`.

Since the root always satisfies `H` transitively down every path (the invariant composed along a root-to-node path implies the root is ≤ every descendant), and `H` holds for all edges after each operation, `A[1]` is always the global minimum — proving `ExtractMin` is correct.

Tradeoffs. The array-heap gives excellent constants and cache locality (it is contiguous memory, unlike pointer-based trees), but plain heaps do not support `DecreaseKey` in O(log n) unless the caller can supply the element's current index — hence the index map is not optional for graph algorithms, it is required infrastructure. Searching for an arbitrary key (not via the map) costs `O(n)`, since the heap gives no ordering information beyond parent-child. Merging two heaps of size `n` and `m` costs `O(n + m)` for binary heaps (rebuild), whereas mergeable heaps (binomial heaps, Fibonacci heaps, pairing heaps) support merge in `O(log n)` or better — a reason those structures exist despite higher constants. Fibonacci heaps achieve amortized `O(1)` `Insert` and `DecreaseKey` with amortized `O(log n)` `ExtractMin`, improving Dijkstra's asymptotic bound on dense graphs, but their large constants and implementation complexity mean binary heaps (or 4-ary heaps, or pairing heaps) usually win in practice.

Trace Dijkstra's algorithm on a small weighted graph, exercising `Insert`, `ExtractMin`, and `DecreaseKey` together — the operation triple that defines the priority-queue ADT in this article's scope. Graph: vertices `S, A, B, C, D`. Edges: `S–A (4)`, `S–B (1)`, `B–A (2)`, `B–C (5)`, `A–C (1)`, `C–D (3)`, `B–D (8)`. Initialize `dist[S]=0`, all others `∞`, and insert all five vertices into a min-heap keyed by `dist`.

Final distances: `S:0, B:1, A:3, C:4, D:7`. Each `DecreaseKey` call needed `O(1)` lookup of the vertex's array index (via the index map) followed by an `O(log n)` sift-up — for `n = 5` this is at most 3 swaps, matching `⌊log₂5⌋ = 2` levels of possible movement. Across the whole run, the algorithm performs `n` `ExtractMin` calls and up to `m` `DecreaseKey` calls (`m` = number of edges), giving the classic bound `O((n + m) log n)` for heap-based Dijkstra — exactly the complexity contributed by the priority queue, since graph traversal itself is `O(n + m)`.

The priority queue's practical form crystallized with the invention of the binary heap for heapsort, but the underlying idea — service by priority rather than arrival order — predates the data structure by decades in operations research and scheduling theory.

Operating system schedulers use priority queues to select the next process or thread to run, often keyed by dynamic priority that ages waiting jobs to prevent starvation. Network routers and quality-of-service systems queue packets by priority class. Discrete-event simulators — from network simulators to physics engines — use a priority queue keyed by event time to always process the next chronological event, an application sometimes called an "event calendar." Huffman coding builds an optimal prefix code by repeatedly extracting the two lowest-frequency nodes from a priority queue and merging them, directly using `ExtractMin` and `Insert`. Dijkstra's shortest-path and Prim's minimum-spanning-tree algorithms are the textbook demonstrations of `DecreaseKey` in action, and both are foundational to routing protocols (OSPF-style link-state routing) and network design tools. Many language standard libraries expose a priority queue directly — C++'s `std::priority_queue`, Java's `PriorityQueue`, Python's `heapq` module — each backed by a binary heap essentially identical to the one described here. Understanding this ADT is also the natural bridge to more advanced ordered structures such as Skip Lists, which support similar ordered-access patterns with probabilistic balancing instead of an implicit tree, and to mergeable heap variants used in advanced graph algorithms.

Ask the tutor: How would you modify the binary-heap priority queue to support efficient merge of two priority queues, and what structure would you switch to for that?