Data Structures and Algorithms
|7.2 Heap Sort
We noted earlier, when discussing
that, as well as their use in priority queues,
they provide a means of sorting:
Addition and deletion are both O(logn)
operations. We need to perform n
additions and deletions, leading to an
We will look at another efficient sorting
and then compare it with Heap sort.
- construct a heap,
- add each item to it (maintaining the heap property!),
- when all items have been added,
remove them one by one (restoring the heap property as
each one is removed).
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.
- 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
Heap Sort Animation
This animation was written by Woi Ang.
||Please email comments to:|
© John Morris, 1998