Why is heapify linear?

[Tim Peters]

[Scott David Daniels]
> 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.

I don't know -- it's not obvious that heapification can be done in
worst-case linear time, and indeed that wasn't realized at first.

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

I don't recall much consistency about this no matter how far back we
look,  For example, quicksort was always always described as an N log
N sorting method in my experience, despite that its worst case is
quadratic.  So I've always qualified O() claims with the intended
measure, unless min, max and mean are the same.  For example, finding
the smallest element in a list is O(n) regardless.  Since just finding
a minimum is O(n) on its own, it's initially surprising that
heapification is also O(n)!