linguistic:paraphrasing, information:highlighting
Pseudocode

The following is a simple way to implement the algorithm in pseudocode. Arrays are zero-based and swap is used to exchange two elements of the array. Movement 'down' means from the root towards the leaves, or from lower indices to higher. Note that during the sort, the largest element is at the root of the heap at a, while at the end of the sort, the largest element is in a.

The sorting routine uses two subroutines, heapify and siftDown. The former is the common in-place heap construction routine, while the latter is a common subroutine for implementing heapify.

The heapify procedure operates by building small heaps and repeatedly merging them using siftDown. It starts with the leaves, observing that the they are trivial but valid heaps by themselves, and then adds parents. Starting with element n /2 and working backwards, each internal node is made the root of a valid heap by sifting down. The last step is sifting down the first element, after which the entire array obeys the heap property.

To see that this takes O (n) time, count the worst-case number of siftDown iterations. The last half of the array requires zero iterations, the preceding quarter requires at most one iteration, the eighth before that requires at most two iterations, the sixteenth before that requires at most three, and so on.

Looked at a different way, if we assume every siftDown call requires the maximum number of iterations, the first half of the array requires one iteration, the first quarter requires one more (total 2), the first eighth requires yet another (total 3), and so on.

This totals n /2 + n /4 + n /8 + ⋯ = n⋅(1/2 + 1/4 + 1/8 + ⋯), where the infinite sum is a well-known geometric series whose sum is 1, thus the product is simply n.

The above is an approximation. The exact worst-case number of comparisons during the heap-construction phase of heapsort is known to be equal to 2 n − 2 s (n) − e (n), where s (n) is the number of 1 bits in the binary representation of n and e (n) is the number of trailing 0 bits.