Binary Heaps

A binary heap is a complete binary tree, stored in an array, in which every parent is at least as large as its children (a max-heap) or at most as large (a min-heap). It answers one question fast: "which element has the highest priority?" The answer sits at the root, and the structure can be repaired in $O(\lg n)$ time after an insertion or a removal.

That makes the heap the standard implementation of a priority queue, used in heapsort, in Dijkstra's shortest-path algorithm and Prim's minimum spanning tree algorithm, in Huffman coding, and in priority scheduling of processes.

A heap is not a search structure: it does not keep keys sorted and cannot find an arbitrary key quickly. It keeps only enough order to expose the maximum (or minimum).

A binary heap must satisfy two conditions.

The heap property is local (parent versus child), but by transitivity it implies that every node is at least as large as everything in its subtree. Hence the maximum of a max-heap is at the root. Nothing is said about the order between siblings or between different subtrees.

Min versus max. Every statement in this note has a mirror image: swap "max" with "min", "largest" with "smallest" and $\ge$ with $\le$. The examples use max-heaps.

Store the nodes level by level in $A[1..n]$. Then, for $1 \le i \le n$:

where a child index larger than $n$ means the child does not exist. With 0-based arrays the formulas are $\lfloor (i-1)/2 \rfloor$, $2i+1$ and $2i+2$. These notes use 1-based indexing for heaps; check the convention in every question.

Useful consequences for a heap of $n$ elements:

Pseudocode uses 1-based arrays, <- for assignment and A.size for the number of elements currently in the heap.

Precondition: the subtrees rooted at $\text{LEFT}(i)$ and $\text{RIGHT}(i)$ are max-heaps, but $A[i]$ may be smaller than a child. MAX-HEAPIFY moves $A[i]$ down until the subtree rooted at $i$ is a max-heap.

Each level costs at most two comparisons and one exchange, so the time is $O(h_i)$, where $h_i$ is the height of node $i$; from the root that is $O(\lg n)$.

Leaves are already one-element heaps, so the loop starts at the last internal node $\lfloor n/2 \rfloor$. Going downwards in index guarantees that when node $i$ is processed, both of its subtrees are already heaps, which is the precondition of MAX-HEAPIFY.

Input $A = [5, 13, 2, 25, 7, 17, 20, 8, 4]$, $n = 9$, so the loop runs $i = 4, 3, 2, 1$.

Result: the max-heap $25, 13, 20, 8, 7, 17, 2, 5, 4$ after 5 exchanges.

The easy bound multiplies about $n/2$ calls by $O(\lg n)$ per call and gets $O(n \lg n)$. That bound is correct but loose, because most nodes are near the bottom and sift down only a short distance.

A node of height $h$ costs $O(h)$. In an $n$-element heap there are at most $\lceil n/2^{h+1} \rceil$ nodes of height $h$, and for $0 \le h \le \lfloor \lg n \rfloor$ this is at most $n/2^h$ (because $\lceil x \rceil \le 2x$ whenever $x \ge 1/2$). So the total work is at most

using $\sum_{h \ge 0} h x^h = x/(1-x)^2$ at $x = 1/2$. The loop also touches $\lfloor n/2 \rfloor$ nodes, so the time is $\Omega(n)$ as well. Hence BUILD-MAX-HEAP runs in $\Theta(n)$.

An exact count makes this concrete. Each exchange moves a key down one level, so the number of exchanges is at most the sum of the heights of all nodes. For a perfect tree of height $h$ (so $n = 2^{h+1} - 1$) that sum is $n - (h + 1) = n - \lg(n+1)$: 4 for $n = 7$, 11 for $n = 15$, 57 for $n = 63$. Over all $7!$ inputs, the maximum number of exchanges for $n = 7$ is exactly 4 (reached, for example, by the increasing input 1 2 3 4 5 6 7).

Top-down construction is different. Building a heap by $n$ successive INSERT calls costs $O(n \lg n)$ in the worst case (for example, keys arriving in increasing order into a max-heap, where each new key rises to the root). Only the bottom-up method is $\Theta(n)$.

INCREASE-KEY at index $i$ sets the larger value and runs the same while loop from $i$. DECREASE-KEY in a max-heap runs MAX-HEAPIFY from $i$ instead. Each is $O(\lg n)$.

Start from the heap $25, 13, 20, 8, 7, 17, 2, 5, 4$.

Both panels of Figure 4 start from the same original heap $25, 13, 20, 8, 7, 17, 2, 5, 4$: the extract-max panel does not contain the inserted 30, so it returns 25, not 30.

Under unit-cost key comparisons/array accesses, bounds below are worst-case unless marked otherwise. Best cases for insert, extract-max, known-index key update/delete and arbitrary-key search are constant (e.g. no sift needed, delete the last element, or find the root). Find-max is always constant; bottom-up build is linear; min-scan is linear; concatenate-and-build merge is linear for every input. Average-case bounds require a distribution and are deferred. For a binary max-heap with $n$ elements:

Space is $\Theta(n)$ for the array. BUILD-MAX-HEAP, HEAP-EXTRACT-MAX and HEAPSORT all call the displayed iterative MAX-HEAPIFY, so those implementations use $O(1)$ auxiliary workspace. A recursive heapify would instead need $O(\lg n)$ worst-case call-stack space.

Heapsort builds a max-heap, then repeatedly exchanges the root with the last element of the heap, shrinks the heap by one, and sifts the new root down.

For integer $d\ge2$, a $d$-ary heap lets each node have up to $d$ children, still complete and still stored level by level. With 1-based indexing, the children of node $i$ are at indices

For $d = 2$ these reduce to $2i, 2i+1$ and $\lfloor j/2 \rfloor$. Example for $d = 3$: the children of node 2 are at 5, 6 and 7, and the parent of node 10 is node 3.

The height is $\Theta(\log_d n)$; for $n = 100$ it is 4 when $d = 3$ and 6 when $d = 2$. Insert and increase-key cost $O(\log_d n)$ (fewer levels to climb), while extract-max costs $O(d \log_d n)$ because each level compares up to $d$ children. A larger $d$ therefore helps algorithms with many key increases and few extractions.