6.3 Building a heap

6.3-1

Using figure 6.3 as a model, illustrate the operation of $\text{BUILD-MAX-HEAP}$ on the array $A = \langle 5, 3, 17, 10, 84, 19, 6, 22, 9 \rangle$.

$$ \begin{aligned} \langle 5, 3, 17, 10, 84, 19, 6, 22, 9 \rangle \\ \langle 5, 3, 17, 22, 84, 19, 6, 10, 9 \rangle \\ \langle 5, 3, 19, 22, 84, 17, 6, 10, 9 \rangle \\ \langle 5, 84, 19, 22, 3, 17, 6, 10, 9 \rangle \\ \langle 84, 5, 19, 22, 3, 17, 6, 10, 9 \rangle \\ \langle 84, 22, 19, 5, 3, 17, 6, 10, 9 \rangle \\ \langle 84, 22, 19, 10, 3, 17, 6, 5, 9 \rangle \\ \end{aligned} $$

6.3-2

Why do we want the loop index $i$ in line 2 of $\text{BUILD-MAX-HEAP}$ to decrease from $\lfloor A.length / 2 \rfloor$ to $1$ rather than increase from $1$ to $\lfloor A.length/2 \rfloor$?

Otherwise we won't be allowed to call $\text{MAX-HEAPIFY}$, since it will fail the condition of having the subtrees be max-heaps. That is, if we start with $1$, there is no guarantee that $A[2]$ and $A[3]$ are roots of max-heaps.

6.3-3

Show that there are at most $\lceil n / 2^{h + 1} \rceil$ nodes of height $h$ in any $n$-element heap.

From 6.1-7, we know that the leaves of a heap are the nodes indexed by

$$\left\lfloor n / 2 \right\rfloor + 1, \left\lfloor n / 2 \right\rfloor + 2, \dots, n.$$

Note that those elements corresponds to the second half of the heap array (plus the middle element if $n$ is odd). Thus, the number of leaves in any heap of size $n$ is $\left\lceil n / 2 \right\rceil$. Let's prove by induction. Let $n_h$ denote the number of nodes at height $h$. The upper bound holds for the base since $n_0 = \left\lceil n / 2 \right\rceil$ is exactly the number of leaves in a heap of size $n$.

Now assume it holds for $h − 1$. We have prove that it also holds for $h$. Note that if $n_{h - 1}$ is even each node at height $h$ has exactly two children, which implies $n_h = n_{h - 1} / 2 = \left\lfloor n_{h - 1} / 2 \right\rfloor$. If $n_{h - 1}$ is odd, one node at height $h$ has one child and the remaining has two children, which also implies $n_h = \left\lfloor n_{h - 1} / 2 \right\rfloor + 1 = \left\lceil n_{h - 1} / 2 \right\rceil$. Thus, we have

$$ \begin{aligned} n_h & = \left\lceil \frac{n_{h - 1}}{2} \right\rceil \\ & \le \left\lceil \frac{1}{2} \cdot \left\lceil \frac{n}{2^{(h - 1) + 1}} \right\rceil \right\rceil \\ & = \left\lceil \frac{1}{2} \cdot \left\lceil \frac{n}{2^h} \right\rceil \right\rceil \\ & = \left\lceil \frac{n}{2^{h + 1}} \right\rceil, \end{aligned} $$

which implies that it holds for $h$.