Skip to content

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.

All the nodes of height $h$ partition the set of leaves into sets of size between $2^{h − 1} + 1$ and $2^h$, where all but one is size $2^h$. Just by putting all the children of each in their own part of the partition. Recall from 6.1-2 that the heap has height $\lfloor\lg n\rfloor$, so, by looking at the one element of this height (the root), we get that there are at most $2^{\lfloor\lg n\rfloor}$ leaves.

Since each of the vertices of height $h$ partitions this into parts of size at least $2^{h − 1} + 1$, and all but one corresponds to a part of size $2^h$, we can let $k$ denote the quantity we wish to bound.

$$ \begin{aligned} (k - 1)2^h + k(2^{h - 1} + 1) \le 2^{\lfloor\lg n\rfloor} \le n / 2 \\ k \le \frac{n + 2^h}{2^{h + 1} + 2^h + 1} \le \frac{n}{2^{h + 1}} \le \left\lceil \frac{n}{2^{h + 1}} \right\rceil. \end{aligned} $$