Linear Heap algorithm, (buildheap)                   (Carol Zander, CSS 343)
---------------------

Consider the complexity of building a heap using the algorithm which puts all
values into the array, then uses heapify to turn each subtree starting at the
bottom level into a heap and works its way up level by level, until the entire
tree is a heap.  This algorithm is linear.  Since this algorithm does a swap at
each node for exactly the height of the node, proving the following theorem,
proves buildheap is O(N) where N = 2^(h+1) - 1  (2 to the power of (h+1),
then -1).  N is the number of nodes in a complete binary tree.
(Assume h=0 for a tree with just a root, i.e., count edges to compute height.)

Theorem:  For a complete binary tree of height h containing 2^(h+1) - 1 nodes,
          the sum of the heights is 2^(h+1) -1 -(h+1).

(Note that since N = 2^(h+1) - 1 , 2^(h+1) -1 -(h+1) is O(N) .)

Reasoning:  Each time we heapify (move a value up the tree), that count is
        the height of the tree.  That's why we sum them.  When we get the sum
        in the theorem, 2^(h+1) - 1 - (h+1), it is O(N) as the -1 -(h+1)  is
        insignificant relative to 2^(h+1) (formally by definition of big-oh).

Proof:  Sum the height of the tree.  Here we use the definition that says an
        empty tree has height -1; a tree with just a root is height zero.

For example, when h is 3, the sum of the heights is:
      1(3)        +       2(2)      +        4(1)      +   8(0)

Now generalize and write as a formula:
      1(3)        +       2(2)      +        4(1)      +   8(0)
   = 2^0(3-0)     +      2^1(3-1)   +       2^2(3-2)   +  2^3(3-3)
   = 2^0(h-0)     +      2^1(h-1)   +       2^2(h-2)   +  2^3(h-3)
       
       //   \           /      \            /       \            
     // \   / \       // \   //  \        /  \     /  \
   // \ /\ /\ /\    // \ /\ // \ /\     //\\//\\ //\\//\\

     1 branch,        2 branches,          4 branches,
     of length 3      of length 2          of length 1

The double lines show the height count.
                   _h_
So, the sum  S  =  \     
                   /__ 2^i (h-i)
                   i=0

Multiply S times 2, then subtract S, and you're left with S:

2S=           2^1(h)   + 2^2(h-1) + 2^3(h-2) +...+ 2^(h-2)(3) + 2^(h-1)(2) + 2^h
-S= -2^0(h) - 2^1(h-1) - 2^2(h-2) - 2^3(h-3) -...- 2^(h-2)(2) - 2^(h-1)(1) - 0
--------------------------------------------------------------------------------
 S=    -h   + 2^1      + 2^2 * 2  + 2^3 * 3  +...+ 2^(h-2)(3-2) + 2^(2-1)  + 2^h
                       - 2^2 * 1  - 2^3 * 2
                       \_______/  \_______/
                         = 2^2     = 2^3      ...

Subtracting term by term, the terms with 'h' drop out and a power of 2 is left.

         _h_
  = -h + \
         /__ 2^j
         j=1
                 _h_
  = -h - 1 + 1 + \             we're just adding and subtracting one, trick
                 /__ 2^j       (which we do so the summation can start at zero)
                 j=1
               _h_
  =  -h - 1  + \               since 1=2^0, we can start the sum at zero
               /__ 2^j
               j=0

  = -h - 1 + 2^(h+1) - 1

  = 2^(h+1) - 1 - (h+1)

So, we have proven that buildheap is O(2^(h+1)-1-(h+1)) = O(N) .