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+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} \left\lceil \frac{n}{2^{h+1}} \right\rceil O(h) \;\le\; cn\sum_{h=0}^{\infty}\frac{h}{2^{h}} = cn\cdot 2 = O(n),$$

using $\sum_{h\ge0} h\,x^h = x/(1-x)^2$ at $x=\tfrac12$. 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 $\langle 4,1,3,2,16,9,10,14,8,7\rangle$ (1-based): start at index 5, work down, and cascading sift-downs yield the heap $\langle 16,14,10,8,7,9,3,2,4,1\rangle$. The runnable exercises reproduce exactly this.