Why is heapify linear?

[Scott David Daniels]

Josiah Carlson wrote:
> 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
> 
I am feeling incredibly stupid over my post.  Of course this is true.
I hadn't considered the triple-at-a-time operation, and I posted w/o
reviewing the code.  I'll crawl back in my hole and quietly wipe the
egg off my face.


Embarassedly,
-Scott David Daniels
Scott.Daniels at Acm.Org