Heap Trees, Part 2
(Up to Basic Computer Science : Data Trees)

[Part 1] [Part 2]

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