two example runs of heapsort, on an array of length n=26, the other
on an array of length n=36.
In both examples, the items in the array are originally colored brown.
Each step of the <strong>heapify</strong> portion of the algorithm,
shown as one line,
is the execution of <strong>bubbledown(i)</strong> for i running
from n to 1 in reverse order.  The initial item i is indicated in red.
The unprocessed items are still brown, while
the items in the processed portion of the array are shown in green.
When all items are green, the array is in <strong>max-heap order</strong>.
<br>
The main loop of heapsort then begins.  Each iteration consists of
first swapping the maximum item, which is in position 1, with the
last item in the heap.  That maximum item is no longer in the heap,
but instead is in its final position.  Items in final position are
shown in black.
<br>
At each iteration of the main loop, the heap becomes one smaller, and
the fully processed sorted array becomes one larger.
Eventually, the heap is empty and the items are sorted.