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.

From 6.1-7, we know that the leaves of a heap are the nodes indexed by

\[\left\lfloor n / 2 \right\rfloor + 1, \left\lfloor n / 2 \right\rfloor + 2, \dots, n.\]

Note that those elements corresponds to the second half of the heap array (plus the middle element if \(n\) is odd). Thus, the number of leaves in any heap of size \(n\) is \(\left\lceil n / 2 \right\rceil\). Let's prove by induction. Let \(n_h\) denote the number of nodes at height \(h\). The upper bound holds for the base since \(n_0 = \left\lceil n / 2 \right\rceil\) is exactly the number of leaves in a heap of size \(n\).

Now assume it holds for \(h − 1\). We have prove that it also holds for \(h\). Note that if \(n_{h - 1}\) is even each node at height \(h\) has exactly two children, which implies \(n_h = n_{h - 1} / 2 = \left\lfloor n_{h - 1} / 2 \right\rfloor\). If \(n_{h - 1}\) is odd, one node at height \(h\) has one child and the remaining has two children, which also implies \(n_h = \left\lfloor n_{h - 1} / 2 \right\rfloor + 1 = \left\lceil n_{h - 1} / 2 \right\rceil\). Thus, we have

\[ \begin{aligned} n_h & = \left\lceil \frac{n_{h - 1}}{2} \right\rceil \\\\ & \le \left\lceil \frac{1}{2} \cdot \left\lceil \frac{n}{2^{(h - 1) + 1}} \right\rceil \right\rceil \\\\ & = \left\lceil \frac{1}{2} \cdot \left\lceil \frac{n}{2^h} \right\rceil \right\rceil \\\\ & = \left\lceil \frac{n}{2^{h + 1}} \right\rceil, \end{aligned} \]

which implies that it holds for \(h\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用