Building a heap is O(N)

You can build a heap efficiently by stuffing everything in an array and shuffling items around until the heap property (a child is always less than or equal to its parent) is satisfied. You do this by calling top-down heapify first on the leaf nodes (does nothing), then on the nodes one level up, etc etc. up to and including the root node.

Top-down heapify assumes everything below the root is in its place and the root just needs to percolate down to where it belongs. A quick analysis tells us that there are \(N\) items that need to be moved at most \(\log N\) steps down so the worst-case complexity is \(O(N \log N)\), but this bound could be tighter.

We can just assume that the tree is completely full since we’re doing a big \(O\) analysis anyway, so let \(N = 2^{n+1} - 1\) and I won’t be messing about with any constants, just counting the number of swaps. On the top or \(0\)th level (IE at the root) there is one subtree where we need to move the root node at most \(n\) spaces down. At the \(1\)st level there are two subtrees where we must move the root at most \(n-1\) spaces down, \(\ldots\), at the \(n-1\)-th level there are \(2^{n-1}\) subtrees where we need to move the nodes at most \(1\) space down, and at the \(n\)-th level are the leaves, which we don’t need to move. Summing up we need at worst to do

\[ \sum_{k=1}^n k2^{n-k} = 2^n\sum_{k=1}^n k2^{-k} \]

moves. The factor \(\sum_{k=1}^n \frac{k}{2^k}\) looks tricky but in fact it is bounded by a constant. Since each term is positive we can safely say that \(\sum_{k=1}^n \frac{k}{2^k} \leq \sum_{k=1}^\infty \frac{k}{2^k}\), and we can apply the tools of analysis to this series: it converges by the ratio test. IE. if a series \(\sum_{n=1}^\infty a_n\) is such that \(\lim_{n\to \infty} \left | \frac{a_{n+1}}{a_n} \right | < 1\) the series converges absolutely (the premium brand convergence).

We could really stop here, having established that for some constant \(c\) it is true that \[ \sum_{k=1}^n k2^{n-k} = 2^n\sum_{k=1}^n k2^{-k} \leq c2^n = O(2^{n+1} - 1 = N). \]

If you really wanted to you could, having shown that the limit exists, do the common trickery of pulling out a factor \(2\) from the series and getting something like the limit \(S = 2S - 2,\) so \(S = 2.\) But who cares about the constants?