How can building a heap be O(n) time complexity?

Question

Can someone help explain how can building a heap be O(n) complexity?

Inserting an item into a heap is O(log n), and the insert is repeated n/2 times (the remainder are leaves, and can't violate the heap property). So, this means the complexity should be O(n log n), I would think.

In other words, for each item we "heapify", it has the potential to have to filter down once for each level for the heap so far (which is log n levels).

What am I missing?

Answer 1

Your analysis is correct. However, it is not tight.

It is not really easy to explain why building a heap is a linear operation, you should better read it.

A great analysis of the algorithm can be seen here.

---

The main idea is that in the build_heap algorithm the actual heapify cost is not O(log n)for all elements.

When heapify is called, the running time depends on how far an element might move down in tree before the process terminates. In other words, it depends on the height of the element in the heap. In the worst case, the element might go down all the way to the leaf level.

Let us count the work done level by level.

At the bottommost level, there are 2^(h)nodes, but we do not call heapify on any of these, so the work is 0. At the next to level there are 2^(h − 1) nodes, and each might move down by 1 level. At the 3rd level from the bottom, there are 2^(h − 2) nodes, and each might move down by 2 levels.

As you can see not all heapify operations are O(log n), this is why you are getting O(n).

Answer 2

I really like explanation by Jeremy west.... another approach which is really easy for understanding is given here http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

since, buildheap depends using depends on heapify and shiftdown approach is used which depends upon sum of the heights of all nodes. So, to find the sum of height of nodes which is given by S = summation from i = 0 to i = h of (2^i*(h-i)), where h = logn is height of the tree solving s, we get s = 2^(h+1) - 1 - (h+1) since, n = 2^(h+1) - 1 s = n - h - 1 = n- logn - 1 s = O(n), and so complexity of buildheap is O(n).

Answer 3

Lets suppose you have N elements in a heap. Then its height would be Log(N)

Now you want to insert another element, then the complexity would be : Log(N), we have to compare all the way UP to the root.

Now you are having N+1 elements & height = Log(N+1)

Using induction technique it can be proved that the complexity of insertion would be ∑logi.

Now using

log a + log b = log ab

This simplifies to : ∑logi=log(n!)

which is actually O(NlogN)

But

we are doing something wrong here, as in all the case we do not reach at the top. Hence while executing most of the times we may find that, we are not going even half way up the tree. Whence, this bound can be optimized to have another tighter bound by using mathematics given in answers above.

This realization came to me after a detail though & experimentation on Heaps.