Heapsort

NOTE: Because the explanation for Heap Sort involves introducing several concepts, this will be broken down into two parts. This is the first part which explains the concept one needs to understand in order to appreciate how heap sort works.

Heap Sort Part One.
Heap sort algorithm is based on a tree structure called the Heap. This algorithm comes in two flavours and that is "max heap sort", and, "min heap sort". They work exactly the same but based on whether they are "Max" or "Min", the algorithm does the opposite of the other. The algorithm is also an 'In-Place' algorithm because it requires little to no extra memory to perform its sorting. It is also a more interesting of all the algorithms because it uses a tree structure for its sorting which reduces the time to O(log n) for its "heapify" method but is overall O(n log n) because "heapify" is called n times. Even more remarkable is how fast it can get the maximum value (or minimum value) in a max or min heap respectively. The speed is infact O(1) and as I explain how the structure works this will become clear. At the very basic explanation, a max heap sort works by first inserting every element to build a max heap. Then delete each maximum and place it in reverse order. Note that getting the maximum takes only O(1) time. If you have seen the previous algorithms I posted you will notice that this looks similar to selection sort but instead this uses an efficient ADT, the tree structure.


How does the heap work
First, what is a complete binary tree.
To understand how heap sort works we first must understand how a heap works. Consequently to understand that we must first understand what a "complete binary tree" is. The heap relies upon the rules of a complete binary tree in order to function.
A complete binary tree is one where it is completely filled at all levels bar the bottom level which is filled from left to right. In a complete binary tree each leaf is at a depth h or h-1. Since the bottom level is filled from left to right then this property also means each leaf on the left is at h compared to a leaf on its right at h-1.

Lets take a look at fig.1 that shows the correct and incorrect complete binary tree.

Fig. 1.

In Fig 1. The reason the bottom tree is not a complete binary tree is because we can see at the bottom there are two leaf nodes on the left labeled "8" and "9". As we move along the bottom we see another leaf node labeled "10". However while there is yet another, fourth, leaf node at the bottom labeled "11/12" it is not first filling the parent node(5) of the previous node. I.E the placement of the fourth node should first entirely fill the left side as is in top first tree. This is the reason why I labeled the last node in the bottom tree as "11/12" because this node should be 11, not 12 as compared to the top tree. Additionally, the top tree is labeled in the traversal order with which an array representing this tree is structured. This type of traversal is known as 'Level Order Traversal' and is a breadth first traversal method.

For the heap to be a max heap the above order must be maintained but there is another order that must be maintained which separates a Max Heap from a Binary tree. This new order is hinted to by the name "max heap". Each node is added at the end of the tree. This node then is "bubbled up" if it is larger than its parent. It continues to be bubbled up until it is larger than any of its children and smaller than its parent. Once that condition is achieved, the tree is in "heap order".

Lets start by inserting the number 50 into the tree and see what happens:

• It is the only node.
• As the only node all branches are full therefore it is a complete tree.
• The tree is in heap order as it is the largest parent node.

Now lets add number 55 and see what happens:

• The node is added as the last node which is the left most bottom leaf.
• It is bigger than its parent(50) so it swaps position with its parent.
• Node with data 55 is now the parent and node with data 50 is its left child.
• The tree is a complete tree.
• The tree is in heap order for a max heap.

The steps outlined above continues for each node added maintaining the heap order and constructing a complete binary tree.
Let's see an example of this at work. We have the following unsorted array: 30, 50, 17, 55, 25, 20, 18.
After placing it in Heap order we have an array that looks like: 55, 50, 20, 30, 25, 17, 18.
The question on the readers mind might be "Ok, but it's not sorted, and how did this new order appear". First lets look at the property of a max heap from the new result. In array index zero(assuming zero index here) we have the maximum value. It will always be the maximum value in a max heap hence we know how to get it and no comparison need take place, therefore O(1) time.

Let's look at Fig. 2. and see what happens as we add each item to the heap from the initial array.

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

In Fig. 2. we start off at the top left and observe the process taking place up to the top right. Then we move down to bottom left and see the continued process up to bottom right. The final tree at the bottom right when converted to an array in the order labeled in Fig.1. top tree will look like the second array shown above. Immediately we can see that the root is the maximum value.

How to tell, looking at the array, where the parent and its children are.
Looking at the zero-indexed array that represents the max heap, we must be able to tell who the parent is for any given node and conversely who the children are for any given node. The solution is typical for any binary tree and rather trivial. For a node n its children is given by the formula (n*2)+1 for the left child and (n*2)+2 for the right child. To find the parent, we simply reverse the calculation. For a child at node n first we determine if it is a left or a right child. Careful observation of the array and how it is represented in the array will show that the right child is always in the even numbered index in a zero indexed array. There are two ways to determine the parent. First is that we mod the node n with 2 => child mod 2 = 0 means right child. If it is non zero it is a left child. We then apply the appropriate formula to find the parent. If it is the left child then: n/2. If it is the right child then n/2 -1.
The second way is to convert it to a non-zero array which makes the left child always even and the right child always odd. We then use the floor function to get the correct index by simply dividing the child's node index by 2. A floor function will take the lower value of a fraction. For example the values 7.0, 7.1, 7.2, 7.3 etc will always return 7. Thus in a zero indexed array using the second method, the parent of any node n is (n+1)/2 -1. The second method is simpler but relies on a floor function being available in a language. Let's see an example: In our heap array above, the node with  the value of 18 has a parent which is a node with the value 20. 18 is at index 6, and 20 is at index 2. Using the second method of finding 18's parent we have: (6+1)/2 -1 = 7/2 -1  = 3.5 -1. Using our floor function, 3.5 becomes 3 hence 3-1 = 2. Index 2 certainly has the node with the value 20 which is our parent. Lets do the same with node with the value 17 which is at index 5. (5+1)/2 -1 = 6/2 -1 = 3 -1 = 2. Once again we get index two which points to node with the value 20 and hence the correct parent of 17.

This is the time to introduce some code that deals with finding the parent and the children of a parent.

private int GetRoot(int child)
{
  return child % 2 == 0 ? child / 2 - 1 /*Right child*/:
                          child / 2; /*Left child*/
}

private int LeftChild(int root)
{
  return ((root*2)+1); //left child index
}

private int RightChild(int root)
{
  return ((root * 2) + 2); //right child index
}

The method for getting the parent from a given child is called "GetRoot" because at each time we will be dealing with a "subtree". Therefore for that subtree the parent is the root. This method uses the mod version even though C# provides Math.Floor method. The method returns the index where the parent of the child is. The LeftChild and RightChild methods take the index of a node and respectively returns the index of the left/right child. Once again the parameter is called "root" because we will be dealing with subtrees for which the parent is the root of all that follows after it. This concludes the basics of a Heap and how to find the parent from the child and vice-versa.
Next up is how we can use the Heap to make Heap Sort work.

Next: Heap Sort part two.
Previous: Merge Sort.
Landing page: Part One.