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

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.

Answer 2

Hint: Suppose instead of an array you were given an arbitrary binary tree. Can you think of an efficient way to fix any nodes that don't satisfy the heap property?

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

Yes there is: Building a heap.

Answer 5

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