Heapify in O(n)

To turn an arbitrary array into a heap, you might think: push each element. That's O(n log n).

Better: heapify — sift-down from the last non-leaf node toward the root. O(n).

Why O(n) and not O(n log n)? Half the nodes are leaves (sift-down does nothing). A quarter sift down 1 level. An eighth sift down 2 levels. Sum:

n/2 * 0 + n/4 * 1 + n/8 * 2 + ...
= n * (0 + 1/4 + 2/8 + 3/16 + ...)
= n * 1

Used by heapsort: heapify the array (O(n)), then repeatedly pop the max to the back (O(n log n)). Total O(n log n) sort, in-place.

For PRIORITY QUEUES, you'd build the heap from a batch of items in O(n) instead of n inserts at O(n log n).