November 6, 2009 A priority queue is a data structure that
permits insertion of a new element and retrieval of its smallest
member; we have seen priority queues in two previous exercises.
Priority queues permit sorting by inserting elements in random
order and retrieving them in sorted order. Heapsort uses the
heap data structure to maintain a priority queue. The heap is a
tree embedded in an array, with the property that the item at
each index i of the array is less than the children at indices
2i and 2i+1. The key to understanding heapsort is a function we
call heapify that gives the sub-array A[i .. n] the heap
property if the sub-array A[i+1 .. n] already has the property.
Heapify starts at the ith element of the array and swaps each
element with its smallest child, repeating the operation at that
child, stopping at the end of the array or when the current
element is smaller than either of its children. Then heapsort
works in two phases; the first phase forms an initial heap by
calling heapify on each ele