6.3 Building a heap

6.3-1

6.3-2

If we loop the index in a increasing order, when we call MAX-HEAPIFY(A, i), it's possible that the left subtree at root 2i and the right subtree at root 2i + 1 are not max-heap.

6.3-3

Remember that the height of a node is the distance from the node to a leaf, such that the height of a leaf is 0 (and the height of the root is the height of the tree).

In exercise 6.1-7, we proved that for a heap has n elements, the leaves are the nodes indexed by $\lfloor \frac{n}{2} \rfloor + 1, \lfloor \frac{n}{2} \rfloor + 2, \ldots, n$. So there are $\lceil \frac{n}{2} \rceil$ leaves. And the height of leaves is 0, so when h = 0, $\lceil \frac{n}{2^{h + 1}} \rceil = \lceil \frac{n}{2^{0 + 1}} \rceil = \lceil \frac{n}{2} \rceil$. The base case holds.

Now let's consider the inductive step. Suppose there are at most $\lceil \frac{n}{2^h} \rceil$ nodes for height h - 1. And let's cut the leaves for the tree with height h. So it has $n - \lceil \frac{n}{2} \rceil = \lfloor \frac{n}{2} \rfloor$ elements. And it's height becomes h - 1. By induction, the nodes at height h - 1 is $\lceil \frac{\lfloor \frac{n}{2} \rfloor}{2^h} \rceil \leq \lceil \frac{\frac{n}{2}}{2^h} \rceil = \lceil \frac{n}{2^{h + 1}} \rceil$, which is also the number of nodes at height h in the original tree.