AI Horizon: Intelligence and Reason in Computers
Introduction Home Essays Resources Contact Info
Essays
  Basic CS
General AI
Chess AI
Go AI

Resources
  Source Code
AI Tips and Tricks
Books
Links

Other
  Code Journal
Site Updates

An Affiliate of Cprogramming.com
 

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

All content is written and published by the people at or affiliated with AI Horizon <http://www.aihorizon.com/>.
Send any comments and suggestions to [email protected].

Please report any errors to [email protected].