Data Structures and Algorithms
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

Both representations are, of course, equivalent.

Heap Sort Animation
This animation was written by Woi Ang.
Please email comments to:
morris@ee.uwa.edu.au

Continue on to Quick Sort Back to the Table of Contents
©
John Morris, 1998