[Algo] 6.3 Building a heap

Building max-heap
一旦我們有了 MAX-HEAPIFY 這個 subroutine 之後，我們就可以把一個 array 建造成一個 max-heap。因為 MAX-HEAPIFY(A, i) 需要 A[i] 下面的兩個 child 都是 max-heap，所以我們一定得採取 bottom-up 的方式來建造 max-heap。

@{
\proc{Build-Max-Heap}(A)
\li \textit{heap-size}[A] = \;\textit{length}[A]
\li \For i = \lfloor length[A]/2 \rfloor \;\textbf{downto}\; 1
\li \;\;\;\;\proc{Max-Heapify}(A, i)
}@

根據 Exercise 6.1-7，我們可以知道從 $\lfoor n/2 \rfloor + 1$ 到 n  都是 leaves，所以我們可以把每個 leaf 都當作一個長度為 1 的 heap，這樣我們就可以 call MAX-HEAPIFY了。


Running time
在分析 BUILD-MAX-HEAP 之前，根據 Exercise 6.3-3 告訴我們：一個 n-element heap 最多只有$\lceil n/2^{h+1} \rceil$個 node 的 height 為 h，證明的部份我們稍後再提。
因為 MAX-HEAPIFY 的 running time 為$O(h)$，所以整個 BUILD-MAX-HEAP 的 running time 我們可以整理成這樣：
$\sum_{h = 0}^{\lfloor \lg n \rfloor} \lceil \frac{n}{2^{h+1}} \rceil O(h) = O(n\sum_{h = 0}^{\lfloor \lg n \rfloor} \frac{h}{2^h})$

因為$\sum_{h = 0}^\infty \frac{h}{2^h} = \frac{1/2}{(1 - 1/2)^2} = 2$，所以 BUILD-MAX-HEAP 的 running time 可以表達成$O(n\sum_{h = 0}^{\lfloor \lg n \rfloor} \frac{h}{2^h}) = O(n\sum_{h = 0}^\infty \frac{h}{2^h}) = O(n)$，是個 linear time 的 subroutine。