7.2 Heap Sort

We noted earlier, when discussing heaps, that, as well as their use in priority queues, they provide a means of sorting:

1. construct a heap,
2. add each item to it (maintaining the heap property!),
3. when all items have been added, remove them one by one (restoring the heap property as each one is removed).

Addition and deletion are both O(logn) operations. We need to perform n additions and deletions, leading to an O(nlogn) algorithm. We will look at another efficient sorting algorithm, Quicksort, and then compare it with Heap sort. 

Animation

The following animation uses a slight modification of the above approach to sort directly using a heap. You will note that it places all the items into the array first, then takes items at the bottom of the heap and restores the heap property, rather than restoring the heap property as each item is entered as the algorithm above suggests. (This approach is described more fully in Cormen et al.) Note that the animation shows the data

• stored in an array (as it is in the implementation of the algorithm) and also
• in the tree form - so that the heap structure can be clearly seen.

Both representations are, of course, equivalent.