# Why is heapify linear?

Josiah Carlson jcarlson at uci.edu
Thu Nov 4 02:00:43 CET 2004

```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
> 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

```