Trees, Part 2
(Up to Basic
Computer Science : Data Trees)
[Part 1] [Part
Heap sort is one of the fastest sorting algorithms, rivaling
such speed-demons as Quicksort and mergesort. The advantages of
heap sort are that it does not use recursion and that heap
sort works just as fast for any data order. That is, there is basically
no worst case scenario.
First, since the heap we just implemented is an array, you can
just convert the array into a heap with the following algorithm:
(refer back to the code structure on the previous page)
- Call shiftDown() on the parent of
the last element. (Halfway back, remember?)
- Moving left, keep calling shiftDown()
of the parent of the next to last element and so on until the
end of the level is reached.
- Move up a level, and keep calling shiftDown()
on the parent node in the same way.
- Keep repeating the second and third step until you've called shiftDown() on the root node.
Basically, since the heap is an array at heart anyway, you just
call shiftDown() on the parent of the
last child or pair of children, and then keep working your way left
across the array, calling shiftDown()
on each element.
Now that you have a legitamate heap, you can sort it back into
an ordered array. Heap sort works from back to front; it starts
with the last element of the sorted array and then steadily works
towards the front. Just keep calling remove()
and storing the data from back to front until the heap is empty.
Even though this sounds a bit repetative, it really is quite fast,
especially for large numbers of elements. Sometimes, it can be faster
than Quicksort or mergesort just because the heap sort is not recursive.
Although on average heap sort is slower than Quicksort and mergesort,
heap sort is more consistent in its speed. Thus, in applications
where timing may be crucial, heap sort is preferred to Quicksort.
The heap tree and heap sort should be much easier to implement
than the binary search tree. Just follow
the guidelines established above, and the programming shouldn't
trouble you much. The description page for the source code file
will explain how the heap sort is implemented in the code.
Download from Source
Code Repository: trees/heap.h