clrs - ch6 sol'ns
CLRS Chapter 6 solutions
Exercises
6.1-1
What are the minimum and maximum numbers of elements in a heap of height \(h?\)
Sol’n
rough draft:
\[ \begin{align*} \sum_{k = 1}^{h - 1} 2^k & < \# \text{ of elements in heap} \le \sum_{k = 1}^h 2^k. \end{align*} \]
Sol’n
6.1-2
Show that an \(n\)-element heap has height \(\lfloor \lg n \rfloor.\)
Sol’n
6.1-3
Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.