Height (heap)

Height of a Heap A heap storing $n$ keys has height $O(\log n)$. Proof by applying the complete binary tree property:

• Let $h$ be the height of a heap storing $n$ keys.
• Since there are $2^i$ keys at depth $i=0,\dots ,h-1$ and at least one key at depth $h$, we have $n\ge 1+2+4+\dots +2^{h-1}+1$.
• Hence, $n\ge 2^h$ or otherwise $h\le \log n$.