Proofs: Floyd's heap construction

Floyd's method uses fewer than n swaps and 2n comparisons full

This proof shows: time.worst, time.best, time.average, space.extra.

Let $n \ge 1$. For a node $i$, its height $h(i)$ is the largest $h \ge 0$ such that $2^h i \le n$. We write $T(i)$ for the set of nodes of the subtree of $i$.

Lemma 1. $h(i)$ is the largest depth of a node of $T(i)$ below $i$.

Proof. The nodes of $T(i)$ at depth $d$ below $i$ are the indices $2^d i, 2^d i + 1, \ldots, 2^d i + 2^d - 1$ that are at most $n$, by induction on $d$: the children of the indices $2^{d} i$ to $2^d i + 2^d - 1$ are the indices $2^{d+1} i$ to $2^{d+1} i + 2^{d+1} - 1$. So there is a node at depth $d$ exactly when the smallest of them, $2^d i$, is at most $n$. $\square$

Lemma 2. MAX-HEAPIFY$(A, n, i)$ does at most $h(i)$ swaps and at most $2h(i)$ key comparisons.

Proof. Let $i_0$ be the first value of $i$, so the claim is about $h(i_0)$. Each swap moves $i$ one level down inside $T(i_0)$, so by Lemma 1 there are at most $h(i_0)$ swaps. Each iteration does at most 2 comparisons (lines L5 and L6), and an iteration at a leaf does none, because both tests $l \le n$ and $r \le n$ fail. Let $s$ be the number of swaps. There are $s + 1$ iterations. If the last one is at a leaf, the comparisons are at most $2s \le 2h(i_0)$. Else the last node has a child, so it is at depth $s \le h(i_0) - 1$, and the comparisons are at most $2(s + 1) \le 2h(i_0)$. $\square$

Lemma 3. $\sum_{i=1}^{n} h(i) = n - s_2(n)$, where $s_2(n)$ is the number of 1 bits of $n$.

Proof. By the definition, $h(i) \ge h$ exactly when $2^h i \le n$, that is, when $i \le \lfloor n/2^h \rfloor$. So, counting each $i$ once for each $h$ with $1 \le h \le h(i)$,

Write $n = \sum_{j=0}^{L} b_j 2^j$ with $b_j \in \{0, 1\}$. Then $\lfloor n/2^h \rfloor = \sum_{j \ge h} b_j 2^{j-h}$, because the part $\sum_{j < h} b_j 2^j$ is less than $2^h$. Summing over $h \ge 1$ and exchanging the sums,

(The term $j = 0$ adds $b_0 (2^0 - 1) = 0$.) $\square$

Theorem. BUILD-MAX-HEAP does at most $n - s_2(n)$ swaps and at most $2(n - s_2(n))$ key comparisons. Its time is $\Theta(n)$ on each input of size $n$, and its extra space is $\Theta(1)$.

Proof. Line L1 calls MAX-HEAPIFY once for each $i \le \lfloor n/2 \rfloor$. The leaves $i > \lfloor n/2 \rfloor$ have $h(i) = 0$, so by Lemmas 2 and 3 the swaps are at most $\sum_i h(i) = n - s_2(n)$ and the comparisons at most $2(n - s_2(n))$. Each call costs $O(1)$ plus $O(1)$ for each iteration, and each iteration other than the last does one swap. So the time is $O(\lfloor n/2 \rfloor + n - s_2(n)) = O(n)$. Line L1 does $\lfloor n/2 \rfloor$ iterations on every input, so the time is $\Omega(n)$ in the best case too. The method keeps only the indices $i$, $l$, $r$ and $m$ and one key for a swap. $\blacksquare$

Floyd's method builds a max-heap from the keys of the input full

This proof shows: correctness, termination.

Write $T(i)$ for the set of indices in the subtree of node $i$ in the complete binary tree on $\{1, \ldots, n\}$: $i$, its children $2i$ and $2i + 1$ when they are at most $n$, their children, and so on. Say that $T(i)$ is a heap when $A[\lfloor j/2 \rfloor] \ge A[j]$ for each $j \in T(i)$ with $j \ne i$. Each index in $T(i)$ other than $i$ is larger than $i$, because a child has a larger index than its parent.

Lemma (MAX-HEAPIFY). Let $1 \le i \le n$, and assume that $T(2i)$ and $T(2i+1)$ are heaps (when they exist). Then MAX-HEAPIFY$(A, n, i)$ stops, it permutes the keys of the cells of $T(i)$ and changes no other cell, and afterwards $T(i)$ is a heap.

Proof. Let $i_0$ be the first value of $i$. We show that this statement is a loop invariant of line L3, for the current value of $i$:

(D) $i \in T(i_0)$; each edge $(\lfloor j/2 \rfloor, j)$ with $j \in T(i_0) \setminus \{i_0\}$ and $\lfloor j/2 \rfloor \ne i$ holds; and if $i \ne i_0$, then $A[\lfloor i/2 \rfloor] \ge A[c]$ for each child $c$ of $i$ with $c \le n$.

Initialization. $i = i_0$. The edges inside $T(i_0)$ that do not start at $i_0$ are the edges inside $T(2i_0)$ and $T(2i_0+1)$, and these hold because the two subtrees are heaps. The last part is empty.

Maintenance. Lines L4 to L6 set $m$ to an index of a largest key among $A[i]$, $A[l]$ (if $l \le n$) and $A[r]$ (if $r \le n$): after line L5, $A[m] = \max(A[i], A[l])$, and after line L6, $A[m]$ is also at least $A[r]$. If $m = i$, then each edge out of $i$ holds, so with (D) each edge inside $T(i_0)$ holds, and line L7 returns with $T(i_0)$ a heap. Else $m$ is a child of $i$, $y = A[m] > A[i] = x$, and $y \ge A[s]$ for the other child $s$ of $i$, if it exists. Line L8 swaps $x$ and $y$. Then:

• the edge $(i, m)$ holds, because $y > x$;
• the edge $(i, s)$ holds, because $y \ge A[s]$;
• if $i \ne i_0$, the edge $(\lfloor i/2 \rfloor, i)$ holds, because the last part of (D) gave $A[\lfloor i/2 \rfloor] \ge A[m] = y$;
• for each child $c$ of $m$, the edge $(m, c)$ held before the swap, because (D) excluded only the edges out of $i$, so $y \ge A[c]$, and $y$ is now at $i = \lfloor m/2 \rfloor$.

The edges out of $m$ may now fail, and (D) for the new value $i = m$ excludes exactly them. The last point gives the last part of (D) for $m$. Also $m \in T(i_0)$. So line L9 keeps (D).

Termination. Each iteration that does not return replaces $i$ by a child, so the depth of $i$ below $i_0$ grows by exactly 1. The depth is at most the height of $i_0$, so there are at most that many swaps, and then line L7 returns, since a leaf gives $m = i$. Each change is a swap of two cells of $T(i_0)$. $\square$

Theorem. BUILD-MAX-HEAP$(A, n)$ stops, and afterwards $A[1 \ldots n]$ is a permutation of its input and satisfies $A[\lfloor j/2 \rfloor] \ge A[j]$ for each $2 \le j \le n$.

Proof. We show this invariant of the loop of line L1:

(B) before the iteration for $i$, the subtree $T(j)$ is a heap for each $j$ with $i < j \le n$.

Initialization. The first value is $i = \lfloor n/2 \rfloor$. Each $j > \lfloor n/2 \rfloor$ has $2j > n$, so it has no child, and $T(j) = \{j\}$ is a heap. If $n \le 1$ the loop does not run, and the array is a heap.

Maintenance. Let $i \ge 1$. The children $2i$ and $2i + 1$ are larger than $i$, so by (B) their subtrees are heaps. The lemma applies: after line L2, $T(i)$ is a heap, and only cells of $T(i)$ changed. Take $j$ with $i - 1 < j \le n$. If $j = i$, $T(j)$ is a heap. If $j \in T(i)$, then $T(j) \subseteq T(i)$, and a subset of a heap of this form is a heap, because its edges are edges of $T(i)$. Else $T(j)$ and $T(i)$ are disjoint: $j$ is not an ancestor of $i$, because an ancestor of $i$ has an index smaller than $i$. So no cell of $T(j)$ changed, and $T(j)$ is still a heap. This is (B) for $i - 1$.

Termination. The loop runs $\lfloor n/2 \rfloor$ times, and each call stops by the lemma. After the iteration for $i = 1$, (B) with $i = 0$ says that $T(1) = \{1, \ldots, n\}$ is a heap. Each change is a swap, so $A$ is a permutation of its input. $\blacksquare$