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.