With a bit more care, and a divide-and-conquer algorithm, it's possible to show that heapifying can be done with O(n) work.
This page last modified on 24 January 2006.