
For each level we use heapifyDown.
assume S = 1/2 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1)
T = n * ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) = n * ( S - 1/2)
S/2 = 1/4 + 1/8 + 2/16 + 3/32 + 5/64 + 8/128 + . . .
S/4 = 1/8 + 1/16 + 2/32 + 3/64 + 5/128 + 8/256 + . . .
3S/4 = 1/4 + 2/8 + 3/16 + 5/32 + 8/64 + 13/128 + . . . = S - 1/2
Hence S = 2.
and T = n * (S - 1/2) = 3/2 * n
T is O(n)
================================================================================================
http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf
page 45
A more formal math (Derivative) version
