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

Question

Given a array of number, is there a O(n) algorithm to build a max-heap?

Answer 1

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).

Answer 2

Yes there is: Building a heap.

Answer 3

If you use a Fibonacci Heap you get amortized O(1) insertion. You can accordingly build a max heap in amortized O(n) from an array.

The implementation of such, I leave as an exercise*.

_{*Though, there are linked example implementations on the Wikipedia page.}

Answer 4

I don't think so. I think the best you can do is O(log n) or a little better with something like a fib heap.