The Height of a Heap

peek reads the root, so it is $O(1)$. add swims a value up and remove sinks a value down, one swap per level, so each does at most $h$ swaps, where $h$ is the height of the tree. Each also has to find one node first: add needs the next open slot, and remove needs the last node. How that is done depends on how the tree is stored. The next chapter stores the tree in two ways, and both find these nodes in $O(h)$ or less. So add and remove are $O(h)$, and their cost depends on the height of the tree.

The height of a complete tree

We need the height $h$ in terms of the number of elements $n$.

In the search tree chapter we worked this out for a perfect binary tree, where every level is full. Its levels hold $1,2,4,\dots ,2^h$ nodes, which add up to $2^{h+1}-1$, so its height is about ${\log }_{2}n$.

A complete tree of height $h$ has every level full except possibly the last. The full part is levels $0$ through $h-1$, which is a perfect tree of height $h-1$ holding $2^h-1$ nodes. The last level, level $h$, holds at least $1$ node and at most a full $2^h$ nodes. If it held no nodes, the tree would be shorter than $h$. Add the last level to the full part, and the total $n$ falls between

$$2^h\le n\le 2^{h+1}-1.$$

From $2^h\le n$, taking ${\log }_2$ of both sides gives $h\le {\log }_{2}n$. From $n\le 2^{h+1}-1<2^{h+1}$, taking ${\log }_2$ gives ${\log }_{2}n<h+1$, that is, $h>{\log }_{2}n-1$. So the height is between ${\log }_{2}n-1$ and ${\log }_{2}n$, which means it is about $\log n$.

A quick check on the six-node heap we have been drawing, which has height $2$:

               ╭───╮
               │ 1 │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │ 3 │               │ 2 │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ 5 │     │ 4 │      │ 8 │
╰───╯     ╰───╯      ╰───╯

Levels $0$ and $1$ are full, with $1$ and $2$ nodes, and level $2$ holds $3$ of its $4$ slots, for $6$ in all. The bounds say $2^2=4\le 6\le 2^3-1=7$, and ${\log }_{2}6\approx 2.58$, which rounds down to $2$. That is the height.