Heaps & heapsort

A tree that lives in an array

A (binary max-)heap is an array $A$ that we read as a nearly-complete binary tree. No pointers: the shape is encoded by arithmetic on indices. Using 1-based CLRS indexing, for node $i$:

• parent is at $\lfloor i/2\rfloor$,
• left child at $2i$, right child at $2i+1$.

The max-heap property is the single local rule $A[\text{parent}(i)]\ge A[i]$ for every non-root $i$. It says nothing about siblings — only parent-vs-child. Its one powerful consequence: the largest element is always at the root $A[1]$. Because the tree is nearly complete, its height is $\lfloor \lg n\rfloor$, so any root-to-leaf walk does $O(\lg n)$ work.

MAX-HEAPIFY — sink one bad node

MAX-HEAPIFY(A, i) assumes the subtrees rooted at $i$'s children are already heaps but $A[i]$ may be too small. It finds the largest of $A[i]$, $A[\text{left}]$, $A[\text{right}]$; if a child wins, it swaps and recurses into that child — the small value floats down at most $\lfloor \lg n\rfloor$ levels. The recurrence is $T(n)\le T(2n/3)+\Theta (1)$ (a child holds at most $2n/3$ nodes when the bottom level is half full), which the master theorem solves to $T(n)=O(\lg n)$.

BUILD-MAX-HEAP — and why it is $O(n)$, not $O(n\lg n)$

Call MAX-HEAPIFY bottom-up, from the last internal node $\lfloor n/2\rfloor$ down to 1. The leaves $A[\lfloor n/2\rfloor +\mathrm{1..}n]$ are already size-1 heaps, so we skip them; going downward guarantees both children are heaps before we fix a node. The loose bound is $n$ calls $\times O(\lg n)=O(n\lg n)$ — but it is not tight. Most nodes sit near the leaves, where MAX-HEAPIFY is cheap. There are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$, and MAX-HEAPIFY costs $O(h)$ on a height-$h$ node, so the total is

$$\sum _{h=0}^{\lfloor \lg n\rfloor }\lceil \frac{n}{2^{h+1}}\rceil O(h)\le cn\sum _{h=0}^{\infty }\frac{h}{2^h}=cn\cdot 2=O(n),$$

using ${\sum }_{h\ge 0}h{x}^h=x/(1-x{)}^2$ at $x=\frac{1}{2}$. Building a heap is linear.

Worked example — HEAPSORT

Heapsort has two phases. (1) BUILD-MAX-HEAP puts the max at $A[1]$ in $O(n)$. (2) For $i$ from $n$ downto $2$: swap $A[1]\leftrightarrow A[i]$ (the max takes its final sorted slot), shrink the heap by one, and MAX-HEAPIFY the new root. Each of the $n-1$ sift-downs is $O(\lg n)$, so heapsort is $O(n\lg n)$ in every case, and it is in-place ($O(1)$ extra). It is not stable.

Trace BUILD-MAX-HEAP on $⟨4,1,3,2,16,9,10,14,8,7⟩$ (1-based): start at index 5, work down, and cascading sift-downs yield the heap $⟨16,14,10,8,7,9,3,2,4,1⟩$. The runnable exercises reproduce exactly this.