Is there a O(n) algorithm to build a max-heap?

algorithm

Solution

Yes, like in this code:

for (int i = N/2; i >= 0; --i)
    push_heap(heap + i, N - i);

(`push_heap` is a function that accepts a pointer to a heap and the heap size and pushes the top of the heap until the heap conditions are respected or the node reaches the bottom of the heap).

To get why this is O(N) look at the complete binary tree:

- 1/2 elements (last level, i > N/2) are pushed down at most 0 steps -> N/2 * 0 operations

- 1/4 elements (last-1 level, i > N/4) are pushed down at most 1 step -> N/4 * 1 operations

1/8 elements (last-2 level, i > N/8) are pushed down at most 2 steps -> N/8 * 2 operations ...

  N/4 * 1 + N/8 * 2 + N/16 * 3 + ... =

  N/4 * 1 + N/8 * 1 + N/16 * 1 + ... +
            N/8 * 1 + N/16 * 2 + ... =

  N/4 * 1 + N/8 * 1 + N/16 * 1 + ... +    // < N/2
            N/8 * 1 + N/16 * 1 + ... +    // < N/4
                      N/16 * 1 + ... +    // < N/8
                                 ... =    // N/2 + N/4 + N/8 + ... < N

Hope that math is not really too complicated. If you look on the tree and add how much each node can be pushed down you'll see the upper bound O(N).

Problem

Original source