[Algo] Exercise 6.3

Exercise 6.3-2
Why do we want the loop index i in line 2 of BUILD-MAX-HEAP to decrease from $\lfloor length[A]/2 \rfloor$ to 1 rather than increase from 1 to $\lfloor length[A]/2 \rfloor$?
When MAX-HEAPIFY is called, it is assumed that the binary trees rooted at LEFT(i) and RIGHT(i) are max-heaps. If we call MAX-HEAPIFY starting from 1, we cannot guarantee that the binary tree rooted at A[2] and the binary tree rooted at A[3] are both max-heaps. Apparently we violate the assumption of MAX-HEAPIFY.


Exercise 6.3-3
Show that there are at most $\lceil n/2^{h+1} \rceil$ nodes of height h in any n-element heap.
我們用歸納法的方式來證明。
當 h = 0 時，根據 Exercise 6.1-7，我們知道 leaf 的 index 是從 $\lfloor n/2 \rfloor + 1$ 到 n，所以總共有 $n - (\lfloor n/2 \rfloor + 1) + 1 = n - \lfloor n/2 \rfloor \leq \frac{n + 1}{2} \leq \lceil n/2 \rceil$ 個 leaves，很明顯符合題目的要求。
Let $S_h$ be the # of nodes of height h，而且假設 h = k 時原式是成立的。
$\Rightarrow S_{k+1} = \lceil \frac{S_k}{2} \rceil \leq \lceil \frac{n/2^{k+1}}{2}\rceil = \lceil \frac{n}{2^{k+2}} \rceil$
顯然，我們可以從 $S_k$ 成功推導到 $S_{k+1}$。最後當 $h = \lfloor \lg n \rfloor$ 時，因為 $2^h \leq n \leq 2^{h+1} - 1$，所以 $\lceil n/2^{h+1} \rceil \leq \lceil \frac{2^{h+1}-1}{2^{h+1}} \rceil \leq 1$，代表當 h 最後等於 $\lfloor \lg n \rfloor$ 時，原式依然是成立的。所以我們可以成功證明題目所要求的。