Build-Max-Heap

Uses Max-Heapify to completely fix a heap using a bottom up manner

Kjøretid: $O(nlgn)$

Runtime

IGNORE UNDER

$$T(n)=2^h\sum _{i=0}^h\frac{i}{2^i}=\Theta (n)\sum _{i=0}^h\frac{i}{2^i}$$

where $h=lg(n)$, and ${\sum }_{i=0}^h\frac{i}{2^i}$ is average work per node

Since the average work per node converges to a number:

$$\sum _{i=0}^h\frac{i}{2^i}=\Theta (1)$$

Which is why we get

$$T(n)=\Theta (n)$$