CLRS Solutions 6.3 Building a heap

6.3-2

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

Otherwise we won't be allowed to call 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.

The height of binary heap is as following:

A heap of size $n$ has at most $\lceil n/2^{h+1} \rceil$ nodes with height $h$. Key Observation: For any $n > 0$, the number of leaves of nearly complete binary tree is $\lceil n/2 \rceil$. Proof by induction Base case: Show that it's true for $h = 0$. This is the direct result from above observation. Inductive step: Suppose it's ture for $h - 1$. Let $N_h$ be the number of nodes at height $h$ in the n-node tree $T$. Consider the tree $T'$ formed by removing the leaves of $T$. It has $n' = n - \lceil n/2 \rceil = \lfloor n/2 \rfloor$ nodes. Note that the node at height $h$ in $T$ would be at height $h-1$ in tree $T'$. Let $N'_{h-1}$ denote the number ot nodes at height $h-1$ in $T'$, we have $N_h = N'_{h-1}$. By induction, we have $N_h = N'_{h-1} = \lceil n'/2^h\rceil = \lceil \lfloor n/2 \rfloor / 2^h \rceil \leqslant \lceil (n/2)/2^h \rceil = \lceil n/2^{h+1}\rceil$.