Chapter map

Where this sits in CS 300. Chapter 7 is the first time the course builds a non-trivial abstract data type (ADT) — the priority queue — and answers it with the first non-trivial tree-as-array structure — the binary heap. It is also the canonical example of a structure whose right asymptotic only emerges from a non-obvious analysis: build_heap is $O(n)$ , not $O(n \log n)$ , and the proof uses a geometric-series sum over node heights. The “tree stored implicitly in an array” pattern resurfaces in chapter 11 (B-trees and disk-friendly indexing) and chapter 13 (heap sort in the comparison-sort table).

What you add to your toolkit:

The array-as-complete-binary-tree encoding — parent, left, right computed by index arithmetic, no pointers.
The max-heap (resp. min-heap) property as a local invariant that, by induction, implies a global guarantee.
Percolate-up and percolate-down as the two universal heap primitives. Every other heap operation is one of these in a wrapper.
Heap sort as the in-place $O(n \log n)$ worst-case sort that doesn’t need merge sort’s auxiliary buffer.
The priority-queue ADT — the thing every graph algorithm needs (forward ref to chapter 10’s Dijkstra and Prim).
Rotations as a first taste, used here to keep treaps balanced (chapter 9 generalises to AVL and red-black trees with strict invariants).

Mastery checklist — you should be able to, without references:

Convert an array index $i$ to its parent / left-child / right-child indices and back, by hand on a 15-element array.
State the max-heap property at a node and explain by induction why it implies the global “every descendant $\le$ root” claim.
Run max_heapify_up and max_heapify_down by hand on a 7-element array, distinguishing which one fires on insert versus delete_max.
Sketch the geometric-series proof that build_heap is $O(n)$ rather than $O(n \log n)$ — at minimum the “sum of node heights $= O(n)$ ” step.
Explain why heap sort is in-place but merge sort is not, and state when you would pick heap sort over quicksort (worst-case-sensitive workload, no random-access budget) and over merge sort (no auxiliary-buffer budget).
Sketch the priority-queue interface (build / insert / delete_max / find_max) and identify which graph-algorithm step (chapter 10 forward ref) needs each operation.
Distinguish max-heap from BST: locating the minimum element of a max-heap is $\Omega(n)$ (must search the leaves) whereas in a BST it is $O(\log n)$ — and articulate why the two structures are not interchangeable.

Looking ahead. Chapter 9 introduces AVL and red-black trees as the deterministic alternative to treaps for the same “balanced search tree” problem; the rotations you meet in §7.5 are exactly the AVL/RB primitives. Chapter 10 leans on the priority-queue ADT for Dijkstra and Prim (every relaxation is a decrease_key on a min-heap). Chapter 13 places heap sort in the comparison-sort table alongside quicksort, mergesort, and counting sort — the worst-case $O(n \log n)$ in-place sort with the weakest constants but the strongest guarantees.

7.1 Heaps: The Big Idea

The problem first: the priority-queue interface

Before we build any data structure, fix the interface — the abstract job we are trying to do. A priority queue is a collection that supports just four operations on a set of keys:

Three running examples make this concrete:

Router scheduling. A network router holds outgoing packets in a priority queue keyed by QoS class (voice before video before bulk). Every clock tick it delete_maxes to pick the next packet to put on the wire.
OS kernel scheduler. The runqueue is a priority queue keyed by “virtual runtime” (lower = more urgent in a min-PQ); the scheduler delete_mins to pick the next thread, then inserts it back with an updated key when the quantum expires.
Discrete-event simulation. Pending events live in a min-PQ keyed by simulated timestamp; the simulator loop is “delete_min, run that event, possibly insert new events, repeat.”

The fourth example is the one chapter 10 will build on: graph algorithms. Dijkstra (single-source shortest paths) and Prim (minimum spanning tree) both repeatedly extract the next “cheapest” frontier vertex from a priority queue. They are the canonical reason the priority-queue ADT exists in algorithms textbooks.

The two extreme implementations – and why neither wins

Once you fix the interface, the natural question is: what’s the cheapest data structure that supports it? Two trivial answers bracket the design space.

Priority queue as an unsorted (dynamic) array. Append on insert ( $O(1)$ ); on find_max or delete_max, linear-scan the array ( $O(n)$ ). build-from- $n$ items is $O(n)$ . To sort with this PQ, do $n$ inserts ( $O(n)$ total) followed by $n$ delete_maxes ( $O(n^2)$ total). That is selection sort.

Priority queue as a sorted array. Keep the array sorted by key. find_max and delete_max are $O(1)$ (the max sits at the end), but insert has to find its slot and shift, $O(n)$ . PQ-sort with this implementation does $n$ inserts ( $O(n^2)$ total) followed by $n$ cheap delete_maxes. That is insertion sort.

The two extremes show the tension: insert-cheap structures have expensive delete_max, and vice versa. Is there a compromise that does both in $O(\log n)$ ? That is exactly what the binary heap delivers, and it is what the rest of this chapter constructs.

Heaps: the answer

A heap is a binary tree specialized for one job: hand me the max (or min) element, fast, and let me insert or remove in logarithmic time. It is not a BST — it deliberately gives up ordered iteration to gain simplicity and speed on that narrow interface. Where a BST balances every subtree to permit arbitrary search, a heap only cares that the root is the extremum.

The min-heap is the mirror image: swap $\ge$ for $\le$ . The root holds the minimum. Everything we say about max-heaps inverts cleanly.

What a heap is not

A quick check: in the BST from chapter 6, node->left < node < node->right. In a max-heap, node->left $\le$ node and node->right $\le$ node, but node->left and node->right are unordered with respect to each other. Two completely different invariants.

Why not just use a sorted list?

We already have structures that hand over the max in $O(1)$ :

A sorted array: max is at the last index. Remove: $O(1)$ . Insert: $O(n)$ to find the spot and shift.
A BST: max is at the rightmost node. Insert/remove: $O(h) = O(\log n)$ balanced, $O(n)$ skewed.
A sorted linked list: max at the tail. Insert: $O(n)$ .

A heap beats all of these for the “give me the max, keep handing me max, occasionally insert new stuff” workload:

::: center Structure Peek max Remove max Insert Notes

Sorted array $O(1)$ $O(1)$ $O(n)$ shifts on insert Sorted linked list $O(1)$ $O(1)$ $O(n)$ scan on insert Unsorted array $O(n)$ $O(n)$ $O(1)$ rescan per op Balanced BST $O(\log n)$ $O(\log n)$ $O(\log n)$ overkill Max-heap $\mathbf{O(1)}$ $\mathbf{O(\log n)}$ $\mathbf{O(\log n)}$ perfect fit :::

The heap trades away ordered iteration and arbitrary search (which we don’t need for this workload) to get $O(\log n)$ insert with $O(1)$ peek.

The canonical use case: priority queues

A priority queue is an abstract data type that supports insert(item, priority), extractMax() (or extractMin()), and peek(). Heaps are the standard implementation. Real-world examples:

OS process schedulers: ready processes live in a max-heap keyed by priority; the scheduler extracts the highest-priority ready process on each quantum.
Online support queues: customers live in a min-heap keyed by “order of arrival + urgency bonus” — whoever has the lowest number (highest effective priority) gets the next agent. This is a common running example in textbooks.
Dijkstra / A* / Prim: graph algorithms repeatedly extract the next “cheapest” frontier node. A min-heap makes those $O((V+E) \log V)$ .
Event simulations: an event-loop heap keyed by simulated timestamp lets you pop “next event” efficiently.
Top- $k$ queries: maintain a min-heap of size $k$ ; for each incoming item, if it’s bigger than the heap’s min, pop and push. Net $O(n \log k)$ instead of $O(n \log n)$ for “top 10 from a stream of a million.”

The two core operations

Every heap algorithm reduces to two primitives. In a max-heap:

Both run in $O(\log n)$ because the tree is kept complete — every level is full except possibly the last, which fills left-to-right. Completeness forces height $= \lfloor \log_2 n \rfloor$ , so a single root-to-leaf path is logarithmic.

Insert: percolate up

Place the new node in the next available slot (leftmost position on the deepest level, extending to a new level if the current one is full). This preserves completeness.
Compare the new node to its parent. If it’s larger, swap. Repeat until the parent is larger or we reach the root.

Walk-through: insert $42$ into

::: center :::

Step 1: attach $42$ as right child of $40$ (first empty slot):

::: center :::

Step 2: $42 > 40$ ? Yes. Swap.

::: center :::

Step 3: $42 > 50$ ? No. Stop. Heap property restored.

Remove (max): replace-and-percolate-down

Save the root’s value (that’s the answer we return).
Take the last node (rightmost leaf of the deepest level) and put it at the root. Delete the now-duplicate last slot. This preserves completeness but usually breaks the heap property at the root.
Percolate down: compare the new root against its two children. If the larger child is greater than the node, swap with that child. Repeat until no larger child exists or the node reaches a leaf.

The “replace with last then percolate down” dance is the whole algorithm. You’re not finding a replacement by careful search — you grab the structural last node to keep the tree complete, and then let percolate-down sort out the resulting local violation.

In the C++ STL

std::priority_queue is a max-heap by default, built on top of std::vector:

#include <queue>
std::priority_queue<int> pq;        // max-heap of ints
pq.push(30); pq.push(50); pq.push(40);
std::cout << pq.top();              // 50
pq.pop();
std::cout << pq.top();              // 40

For a min-heap, pass std::greater:

std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;

Section 7.2 will show how the tree is actually stored — surprise, not with pointers. Sections 7.3 and 7.4 formalize percolateUp and percolateDown. Section 7.5 builds the priority-queue ADT on top.

7.2 Heaps Stored in Arrays

Here’s the twist: the binary tree in chapter 6 uses a TreeNode struct with left, right, (parent) pointers per node. A heap uses nothing of the sort. A heap is almost always stored as a plain array, with all parent/child relationships computed by index arithmetic. No pointers, no allocations per node, no cache misses on node traversal. This is the single biggest reason the heap is the go-to priority queue in practice.

Example

::: center :::

stored as:

::: center Index 0 1 2 3 4 5 6

Value 57 42 19 13 6 7 15 :::

Check: parent(4) = (4-1)/2 = 1, so parent of $6$ is $42$ — correct. leftChild(2) = 5, so left child of $19$ is $7$ — correct.

Why the local property implies a global guarantee

The max-heap property is stated locally: each node is $\ge$ its two children. The defnbox in §7.1 claimed by transitivity that this implies the global fact “the root’s key is $\ge$ every descendant’s key.” Here is the proof.

Claim. For every node $i$ and every descendant $j$ of $i$ , $\text{key}(i) \ge \text{key}(j)$ .

Proof by induction on $d = \text{depth}(j) - \text{depth}(i)$ , the depth difference between $j$ and $i$ .

Base case ( $d = 1$ ). If $d = 1$ , then $j$ is a child of $i$ . The local max-heap property at $i$ states $\text\{key\}(i) \ge \text\{key\}(j)$ directly.

Inductive step ( $d \ge 2$ ). Assume the claim holds for every pair with depth difference $< d$ . Let $j$ be a descendant of $i$ at depth $d$ below $i$ , and let $k$ be the parent of $j$ . Then $k$ is a descendant of $i$ at depth difference $d - 1$ , so by the inductive hypothesis $\text{key}(i) \ge \text{key}(k)$ . The local max-heap property at $k$ gives $\text{key}(k) \ge \text{key}(j)$ . Chaining, $\text{key}(i) \ge \text{key}(k) \ge \text{key}(j)$ . Q.E.D.

Consequence. Setting $i$ to the root: the root’s key is $\ge$ every key in the heap, so find_max is just “return $h[0]$ ” in $O(1)$ . The minimum, by contrast, can be anywhere among the leaves, so find_min on a max-heap is $\Omega(n)$ — you have to look at all of them. We will revisit this in §7.6.

Why arrays beat pointers here

::: center Pointer-based tree Array-based heap

3 pointers per node (24 B on 64-bit) No per-element overhead Cache miss per child jump Cache-friendly (children are 1—2 cells ahead) new/delete per insert/remove vector grows amortized $O(1)$ Works for arbitrary tree shapes Requires completeness :::

For a heap of a million ints: pointer representation is $\approx 28$ MB of overhead beyond the values themselves; array representation is $\approx 0$ overhead. The array form is also a contiguous memory block, so sequential scans (like heapsort) are prefetch-friendly.

Percolate-up, array version

Starting at some index i where the heap property might be broken upward, walk toward the root swapping with parent while the child is larger:

void maxHeapPercolateUp(int i, std::vector<int>& h) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (h[i] <= h[parent]) return;          // heap property satisfied
        std::swap(h[i], h[parent]);
        i = parent;                              // continue from new position
    }
}

The loop runs at most $\lfloor \log_2 n \rfloor$ times because each iteration halves the index. That’s the $O(\log n)$ insert bound.

Percolate-down, array version

Starting at some index i (usually 0, after the root was replaced), walk toward the leaves swapping with the larger child while a child is larger than the node:

void maxHeapPercolateDown(int i, std::vector<int>& h) {
    int n = static_cast<int>(h.size());
    while (2 * i + 1 < n) {                      // at least one child exists
        int left  = 2 * i + 1;
        int right = 2 * i + 2;
        int biggest = left;
        if (right < n && h[right] > h[left]) biggest = right;
        if (h[i] >= h[biggest]) return;          // heap property satisfied
        std::swap(h[i], h[biggest]);
        i = biggest;
    }
}

Watch the three subtleties:

Check left first. If 2*i+1 >= n, i is a leaf and we’re done.
Right might not exist. That’s why the right comparison is guarded by right < n.
Swap with the larger child, not an arbitrary child. If you swap with the smaller, the larger child becomes the new root and you’ve created a new violation below.

The loop runs at most $\lfloor \log_2 n \rfloor$ times (each iteration doubles the index). That’s the $O(\log n)$ extract-max bound.

Insert and extract, array versions

void maxHeapInsert(std::vector<int>& h, int value) {
    h.push_back(value);                          // step 1: preserve completeness
    maxHeapPercolateUp(h.size() - 1, h);         // step 2: restore heap property
}

int maxHeapExtract(std::vector<int>& h) {
    int top = h[0];
    h[0] = h.back();                             // move last to root
    h.pop_back();                                // shrink
    if (!h.empty()) maxHeapPercolateDown(0, h);
    return top;
}

Two functions, each $O(\log n)$ worst case, each three lines of logic. No tree allocations, no node structs, no parent pointers. The index formulas are the whole trick.

7.3 Heapsort

Heapsort is the sorting algorithm you get almost for free once you have a heap. The idea: turn an array into a max-heap, then repeatedly extract the max to the end of the array. You end up with an array sorted in ascending order, using no extra memory beyond the input array itself.

Two phases:

Heapify the input array in place — transform it into a valid max-heap.
Sort down: swap arr[0] (the max) with the last unsorted slot, shrink the heap by one, and percolate the new root down. Repeat until the heap is empty.

Both phases use one primitive: maxHeapPercolateDown from section 7.2.

Heapify: bottom-up heap construction

Given an arbitrary array, how do we make it a max-heap? Naive approach: insert all elements one by one, each an $O(\log n)$ operation — total $O(n \log n)$ . There is a better way.

The last internal node is at index $\lfloor n/2 \rfloor - 1$ , because nodes at index $\ge \lfloor n/2 \rfloor$ are leaves (their first child index $2i + 1$ is out of range).

void heapify(std::vector<int>& a) {
    for (int i = static_cast<int>(a.size()) / 2 - 1; i >= 0; --i)
        maxHeapPercolateDown(i, a);
}

Bottom-up build-max-heap on \texttt{[7,3,5,6,2,0,3,1,9,4

$n = 10$ , so the last internal node is at index $\lfloor 10/2 \rfloor - 1 = 4$ . We call percolateDown(i) for $i = 4, 3, 2, 1, 0$ in turn. At each step, the subtree rooted at the index being processed becomes a valid max-heap; everything below it is already a valid max-heap from prior steps.

::: center Step 0 1 2 3 4 5 6 7 8 9 Action

start 7 3 5 6 2 0 3 1 9 4 input array $i=4$ 7 3 5 6 4 0 3 1 9 2 swap $a[4]=2$ with larger child $a[9]=4$ $i=3$ 7 3 5 9 4 0 3 1 6 2 swap $a[3]=6$ with larger child $a[8]=9$ $i=2$ 7 3 5 9 4 0 3 1 6 2 $a[2]=5 \ge \max(0,3)$ , no swap $i=1$ 7 9 5 6 4 0 3 1 3 2 swap $a[1]=3$ with $a[3]=9$ , then $a[3]=3$ with $a[8]=6$ $i=0$ swap 1 9 7 5 6 4 0 3 1 3 2 swap $a[0]=7$ with $a[1]=9$ $i=0$ swap 2 9 7 5 6 4 0 3 1 3 2 at index 1, $a[1]=7 \ge \max(6,4)$ , stop :::

Final: [9, 7, 5, 6, 4, 0, 3, 1, 3, 2]. Spot-check: $9 \ge \{7, 5\}$ , $7 \ge \{6, 4\}$ , $5 \ge \{0, 3\}$ , $6 \ge \{1, 3\}$ , $4 \ge \{2\}$ . Valid max-heap. Total work: 5 calls to percolateDown doing 1, 1, 0, 2, 1 swaps respectively — 5 swaps total for $n = 10$ , well under the worst-case $n \log_2 n \approx 33$ that a one-by-one insert sequence would do.

Why heapify is O(n), not O(n \log n)

This is the cleverness of bottom-up construction, and it catches most students off-guard on exams.

Percolate-down at index $i$ does work proportional to the height of the subtree rooted at $i$ , not the total height of the tree. A leaf has height 0 (does no work). A parent of leaves has height 1 (at most 1 swap). The root has height $\log n$ . Summed over all nodes: