Show that an \(n\)-element heap has height \(\lfloor \lg n \rfloor\).

Based on Exercise 6.1-1, a heap of height \(h\) is a complete tree of height \(h - 1\) with an additional level that has between \(1\) and \(2^h\) nodes.

\[\begin{split} 2^h & \leq n & \leq 2^{h+1} - 1 \\ 2^h & \leq n & < 2^{h+1} \\ \lg(2^h) & \leq \lg n & < \lg (2^{h+1}) \\ h & \leq \lg n & < h + 1 \\ \end{split}\]

Because \(h\) is an integer, we can say that \(h = \lfloor \lg n \rfloor\).