Heap Sort Part Two

Heap Sort Part Two

In part one of heap sort we covered what a max heap is and how a max heap works. This was important in order for part two to make sense. In this part I will describe how a max heap can be utilised to produce a sorting algorithm that works in a similar way to selection sort but uses an efficient ADT, the max heap.

Firstly, how do I figure that max heap sort works in a similar way to selection sort? Selection sort works by getting the index of the maximum value. It then swaps that with the element at the end of the current index-able end point. The swapping operation is followed by reducing the problem domain by one and repeating the process with the new end point. The time taken to do that is n, and it runs n passes therefore has a O(n^2) running time. Max heap sort uses the max heap to get the largest value. This value is always O(1) because it is always at the front of the array and it is swapped with the last element of the array and then the problem domain is reduced by one. The last element of the current problem domain is the last leaf node of the max heap tree. When the above swap is done, this leaf node becomes the new root and breaks the "Heap Order". This order needs to be restored by applying a method known as "heapify". Essentially the root is percolated down until the heap order is restored for a max heap. Since this takes O(log n) time and is called n times the total cost then for heap sort is "n * 1 * log n" which is O(n log n). That is a much better result than selection sort.

In part one, I only showed code for getting child and parent, I did not show the code for max heap. The reason is that the process for max heap sort is very small and to aid in its explanation I wanted to discuss heapify at the same time. This discussion is essential to understand what is happening as max heap sort is progressing. However that restricted me from also showing the code for creating a max heap because it uses the heapify method. Without further ado let us take a look, first, at max heap code:

private void MaxHeap(ref int[] array)
{
  for (int i = (array.Length - 2) / 2; i >= 0; i--)
    MaxHeapify(ref array, i, array.Length);
}

Fig. 1.

In the above code we first find the index of the last root in the array sequence. This is given by (array.Length - 2) / 2. We have array.Length-2 because first root is i -1/2 since i is zero indexed, array.Length-1 -1 /2 therefore array.length-2/2. The last root in this context means in a level order traversal the last node that is the last parent node and not a last leaf node. Example in Fig. 1 node labeled 20 is the last root node. The level order array for that is: 55, 50, 20, 30, 25, 17, 18. Using the above equation we will see that it accurately picks node labeled 20 as the last root. First the length is seven. Thus (7 - 2)/2 = 5/2 = 2.5 which is 2 because C# takes the floor of that decimal. Index two does indeed contain 20 which is the last root of the max heap tree in fig. 1. However please be aware that when we are running MaxHeap we are actually building the heap from an unsorted array. This means the array is neither sorted nor is it in heap order. Remember from part one that the first step is to build the heap and that is what MaxHeap is doing in an in-place fashion. You can write this function in various ways, for example, you could start at index zero and go up to the index of the last root. I chose to start at the last root and work down to the first root because it feels more intuitive that way when you are working through on paper and draw a tree. For each root, the heapify method is called to ensure that each subtree processed has the largest value than anything below it.

Let's look at the code for MaxHeapify:

private void MaxHeapify(ref int[] array, int root, int length)
{
  int left = LeftChild(root);
  int right = RightChild(root);
  int j = root;
  if (left < length) j = array[left] > array[root]? left : root;
  if (right < length) j =  array[right] > array[j] ? right : j;
  if (root != j)
  {
    Swap(ref array, root, j);
    MaxHeapify(ref array, j, length);
  }
}

Line by line lets look at how this works.
First we retrieve the left child and right child indices of the root. Next we create a new variable and assign it the index of the root. What follows is a relation that is transitive. It follows that if left child is bigger than root and right child is bigger than left child, then right child is bigger than root. Or formally if A > B > C then by transitivity, A > C. The result of the two "if"statements is that either variable 'j' will contain the index of a new root that has a value bigger than current root or it will index the same as current root. The conditionals left < length and right < length should be obvious but I will explain. If a node has no left child then the left child index returned will be larger than the size of the array and similarly for the right child. As an interesting note to think about is that in a complete binary tree if a node does not have a left child, it most certainly will not have a right child.

Once the root index is found then the code checks if the root is the same or different. If it is a different root then we apply a swap because the new root will certainly be one that has a larger value than the starting root. We then recurse to ensure all nodes of the subtree is traversed and that we have the maximum root for this subtree. When this recursive method completes, command returns to MaxHeap method which will look at the next root, and so on until all roots are heapified and the tree is in heap order.

Using The Max Heap to perform Sorting.
We have now thoroughly covered Max Heap in terms of building the Heap however we have not fully covered what happens when we pop off the root. Infact I saved that so I can write it under this heading because that action is the reason max heap sort works! Lets graphically see what happens as shown in Fig. 2.

Fig. 2. Click on image to enlarge in order to see details.

As seen in fig. 2. we start with the initial tree which is in max heap order. We remove the root which we have come to know will be the largest value. The value is 55 in this tree, and we replace the root with the last leaf node which is of value 18 in this tree. We then percolate down value 18 until heap order is restored. We now have value 50 as root which is now the largest value so we remove that and replace it with the last leaf which is now node with value 17. We percolate down 17 until max heap order is restored. This continues on until all the values are popped and we are left with the resulting array: 17, 18, 20, 25, 30, 50, 55. This is now the sorted array in ascending order! If you have not guessed already, the process of percolating down is known as heapify because it restores the heap order.

Lets look at this from the array's perspective on what is happening.
Our initial array in max heap order: 55, 50, 20, 30, 25, 17, 18.
I will not label the steps, you need to follow the steps based on steps in the tree in fig. 2.
18, 50, 20, 30, 25, 17, 55.
50, 18, 20, 30, 25, 17, 55.
50, 30, 20, 18, 25, 17, 55.
17, 30, 20, 18, 25, 50, 55.
30, 17, 20, 18, 25, 50, 55.
30, 25, 20, 18, 17, 50, 55.
17, 25, 20, 18, 30, 50, 55.
25, 17, 20, 18, 30, 50, 55.
25, 18, 20, 17, 30, 50, 55.
17, 18, 20, 25, 30, 50, 55.
20, 18, 17, 25, 30, 50, 55.
17, 18, 20, 25, 30, 50, 55.
18, 17, 20, 25, 30, 50, 55.
17, 18, 20, 25, 30, 50, 55. Done.
As a reminder, the tree in Max heap sort is converted to the array in level-order traversal method. So to follow the above array with the tree, convert each tree to each respective array. Leave the bold faced elements in the array as these are sorted elements and will be missing from the tree. The above array shows how max heap sort is easily implemented as in-place. The most interesting thing we notice is that as we remove the root, what we are actually doing in the array is swapping it with the last element in the current problem domain. So our problem domain starts with seven elements. After the first swap and heapify our problem domain shrinks to six, then five, and so on. At each time we are swapping the first element with the last element of the current domain which directly translates to removing the root and replacing it with the last leaf node.

I will now show the code that does max heap sorting:

public void MaxHeapSort(ref int[] array)
{
  MaxHeap(ref array);
  MaxHeapSort(ref array, array.Length-1);
}

private void  MaxHeapSort(ref int[] array, int tail)
{
  while (tail > 0)
  {
    Swap(ref array, 0, tail--); //Pop max value.
    for (int i = (tail - 1) / 2; i >= 0; i--) MaxHeapify(ref array, i, tail + 1);
  }
}

The first method called MaxHeapSort with one parameter takes the array and calls MaxHeap to build the max heap. It then calls the overloaded method MaxHeapSort with two parameters and passes it the reference to the array with the length taking into account the zero index array.

In the MaxHeapSort overloaded method with two parameters the first parameter is the reference to the array passed to it but the second parameter is the last cell of the current problem domain. This domain is represented by the "tail" variable and is decremented as the problem domain shrinks. First we see the while loop which checks if the remaining cells to pop is more than 1, stops otherwise as at that point the array will be sorted. Inside the while loop element zero is swapped with the element at tail. This is the O(1) time I mentioned because we know that always the zeroth index will have the largest value in a max heap. After swapping, the heap property is lost so we perform a heapify operation. This is done by getting the last root of this problem domain and heapifying each until heap order is restored. The while loop will run n times, reducing the problem domain each time until we have a array that is sorted in ascending order.

I left max heap sort last in this part one of "Sort and search algorithms using C#" because it needs the longest explanation and because it combines a number of concepts. However, like mergesort, this algorithm is always O(n log n). Heap sort is better used where you want an in-place algorithm and want the ability to get the maximum value in O(1) time complexity.

This concludes the algorithms for sorting, but there is one more topic to cover. That is a searching one. I will only cover one searching algorithm, called the binary search.

Next: Binary Search.
Previous: Heap Sort part one.
Landing page: Part One.