Why is heapify linear?

[Scott David Daniels]

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.

Tim Peters wrote:
 > [Scott David Daniels]
 >> The "hand wave" on dict building is because I am still stuck in the
 >> sad old world where, when we said O(1), we meant "worst case linear."
 > I don't recall much consistency about this no matter how far back we
 > look,
Sorry, the we was more from my personal history (a particular institute
and some of Knuth's classes), not all-of-CS history.  I look at O(n) or
linear and think "worst-case," as did everyone in our study groups or
hanging around our education research institute.  I wasn't working
towards a doctorate at the time, and only read odd papers for "fun."
I had managed to make a few things infeasibly fast with priority queues
back then, knew their implementation as heaps, and erroneously thought
I knew rough properties.

Isaac To wrote:
  <A beautiful explanation of "why linear worst-case">
Thanks, Isaac for writing such a short, clear explanation.  I'll still
do the Floyd penance, but now I know the gist and can read for it.  The
first exposition of a principle is often not as obviously clear as
subsequent attempts.

-Scott David Daniels
Scott.Daniels at Acm.Org