Why is heapify linear?

[Josiah Carlson]

Scott David Daniels <Scott.Daniels at Acm.Org> wrote:
> 
> I am sorry, but in the Python 2.4 description of "heapify", I find the
> description of "Transform list x into a heap, in-place, in linear time,"
> unbelievable.  I understand the hand-wave that makes dictionary building
> linear (though I have a hard time with even that).  Could somebody tell
> me what twist of logic makes "heapify" linear, except in the sense that
> linear is coming to mean "very fast?"

It has to do with the amount of work done by doing the heapify operation
from the bottom up.

Using ugly ascii-art math, we get the following work for heapifying from
the bottom up:

   log(n)   i*n
    SUM    ----
    i=1    2**i

That sum is known to converge to 2n from below (there is a simple
picture that I can present that will prove it to you, if desired). 2n is
O(n). Hence linear.


 - Josiah