Why is heapify linear?

[Josiah Carlson]

Scott David Daniels <Scott.Daniels at Acm.Org> wrote:
> 
> Josiah Carlson wrote:
>   <cost of "heapify from the bottom" and an offer to provide a picture>
>  > (there is a simple picture that I can present that will prove it to
>  > you, if desired).
> At which point I became embarassed at not having done my homework before
> asking.  The sum itself clearly adds to the claimed value, but I hadn't
> even read the heapify code yet and was wishing I could hide.  I presume
> this picture matches Isaac To's ASCII picture.

Nope, I (we) do the summation via picture.  If you break down each term
(i/2**i) into rows:

  1
 ---
  2

  1   1
 --- ---
  4   4

  1   1   1
 --- --- ---
  8   8   8
...

Sum the columns individually:
 --- --- ---
  1  1/2 1/4

Then sum that bottom row...
1 + 1/2 + 1/4 + 1/8 + 1/16 + ...
A nice geometric sum that approaches 2.  Multiply by a factor of n, and
we are done.

I cannot take credit for that picture, I first saw it provided by
Michael Dillencourt (http://www.ics.uci.edu/~dillenco) while I was his
TA.


 - Josiah