Why is heapify linear?

[Scott David Daniels]

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?"

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