|
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:
- 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).
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.
Heap Sort Animation
This animation was written by Woi Ang. |
|
Please email comments to:
|
© , 1998