3.2. Uses of Heaps

There are two main uses of heaps.

The first is as a way of implementing a special kind of queue, called a priority queue. Recall that in an ordinary queue, elements are added at one end of the queue and removed from the other end, so that the elements are removed in the same order they are added (FIFO). In a priority queue, each element has a priority; when an element is removed it must be the element on the queue with the highest priority.

A very efficient way to implement a priority queue is with a heap ordered by priority - each node is higher priority than everything below it. The highest priority element, then, is at the top of the heap. We've just seen that the top element can be retrieved with a single delete operation - O(logN) - and that inserting a new element is also O(logN).

The second application is sorting. HeapSort uses the heap data structure to sort values in exactly the same way as TreeSort used a binary search tree. To sort an array, or list, containing N values there are two steps:

1. insert each value into a heap (initially empty)
2. remove each value form the heap in ascending order (this is done by N successive calls to get_smallest).

(N insert operations) + (N delete operations)

Each insert and delete operation is O(logN) at the very worst - the heap does not always have all N values in it. So, the complexity is certainly no greater than O(NlogN). This is better than the worst-case for TreeSort, which, because you might build a degenerate binary search tree, is O(N*N).

HeapSort is especially useful for sorting arrays. Why? Because heaps - unlike almost all other types of trees - are usually implemented in arrays, not as linked data structures!

Let us see how a tree-structure can be represented in an array.