Sorting Stuff with Heap Sort - Part III

In part I and II of this series, we learnt about Heap Sort and how to construct a heap out of unsorted data. Now, let's move on. Once the heap is constructed, we need to sort it.

You might have noticed that the SIFT function takes a heap size as one of its arguments. If the SIFT function already knows what heap it is working on, why would it be necessary to pass in the heapSize separately? The reason is that SIFT doesn't have to sift a node through the entire heap. It can work with a smaller part of the heap. In the HEAPIFY routine, everytime we invoked SIFT, we passed a constant heap size to it but we would like to be able to specify a smaller heap size if we want. We'll see the reason for this soon.

We already know that the top-most node in any heap is the largest value. In order to sort the heap, what we do is swap the top node (or in other words the 0th element in the list) with the last node in the heap (the element whose index is inputDataList.length()-1). Now our largest value is at the bottom of the heap. Next, we reduce the size of the heap to be sorted and sift the top-most node using the reduced heap size as an argument. The top node, of course, has to be sifted so that we get a proper heap again. We keep swapping and sifting until the size of the heap to be sorted becomes zero.

The following algorithm performs sorting of a heap:

1. i = inputDataList.length()-1
2. while(i > 0)
{
3. SWAP(0, i)
4. SIFT(0, i)
5. i = i - 1
}

That's all there is to it. Here's some C++ code that I had written to augment this series. If the algorithms I've provided seem a bit vague, feel free to look at the code here. Also, check out this nice Heap Sort visualization here.