A heap (balanced binary tree) is a tree that carries for each parent (node) a maximum of $2$ children, while last level always occurs without children and is called leave.The runtime boundary for such a heap is in worst case $O(log(n))$.

We give a short proof sketchfor this by:

(a) deriving the general formula of such a "worst case" balancing operation (root to leave!)
(b) show that the formula has a boundary of $O(log(n))$.

With $n$ we refer to the number of inputs into the algorithm.

1. Assuming the tree has $n+1$ nodes ($i=0,...,n$), given by
   
   $i=0$ with $2^{0}=1$ node
   $i=1$ with $2^{1}=2$ nodes
   $...$
   $i=n$ with $2^{n}$ nodes
   

2. If we balance the worst case path (root to leave) we must sum all possible levels given by
   
   $\displaystyle\sum_{i=0}^{n}2^i$
   We set this formula to:
   

   (1) $\displaystyle\sum_{i=0}^{n}2^i=2^{n+1}-1$

   and proof it next, by induction.

3. START
   $n=0$ gives $1=2^{0}=1=2^{0+1}-1=2^{1}-1=1$

   ASSUMPTION
   By START holds (1), hence we assume (1) also holds for general $n$.

   INDUCTION
   To show that (1) also holds for $n$ $\rightarrow$ $n+1$, we must show that we fulfill
   $\displaystyle\sum_{i=0}^{n+1}2^i=2^{n+2}-1$
   

   Rewriting the sum we get
   $\displaystyle\sum_{i=0}^{n}2^i+2^{n+1}=2^{n+2}-1$
   
   and we know that for the left sum we can use (1), hence we get
   $(2^{n+1}-1)+2^{n+1}=2^{n+2}-1$
   

   now rearranging left side hand we get
   $2^{n+1}+2^{n+1}-1=2^{n+2}-1$
   

   which gives
   $2*2^{n+1}-1=2^{n+2}-1$
   

   and finally
   $2^{n+1}-1=2^{n+2}-1$
   

   to proof that (1) holds.
   
   

We assume $n>0$ to not proof trivial cases and avoid the term $log(0)$. We know each $n$ node binary tree has a worst case balancing of
$2^{n+1}-1$

Now to find height $i$ in terms of $n$ input's we write
$n=2^{i+1}-1$

which gives
$n+1=2^{i+1}$

then applying the logarithm yields
$i=\frac{1}{log(2)}*log(n+1)-1$

now by ignoring constants as
$\frac{1}{log(2)}$, $1$ and $-1$

we see that $i$ is as of $O(log(n))$.