Why is heapify linear?

[Scott David Daniels]

Tim Peters wrote:
> There are no hands waving.  Dict-building is best-case and
> expected-case linear time, but worst-case quadratic time.  For
> heapification, all three are linear.  That's all rigorously provable
> (and typically are so proved in a first course on algorithmic
> complexity).  Google on
> 
>     heapify linear
> 
> to find proofs for heapification bounds.  But you perhaps won't
> *believe* it until you can't deny it <wink>.  So try it:
I stupidly took a simple look before posting, and a better look
immediately after posting.  I feel really stupid for that and
deserve the big clue stick whack.

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 am sure you remember those times.  The "expected-case" or "amortized-
time" silent, rather than stated, still bothers me, not so much in an
irritated way, as in a "my mind still doesn't notice" way.

> ... Note that "the obvious" way to transform a list into a heap is not
> worst-case linear time.  Linear-time heapification is due to Floyd.
This is the bit I didn't notice, and so my knee-jerk from the "obvious"
way -- essentially a half-sort.  As pennance I should read Floyd's paper
(CACM 7, p701, 1964).