Hello friends, In this article I will continue out discussion of the sorting algorithms. And I will discuss Heap sort algorithm with simple and easy example written in C# programming language.
Before that if you want you can read about other algorithms at the below links.
- Quick sort algorithm in C#
- Merge sort algorithm in C#
- Selection sort algorithm in C#
- Insertion sort algorithm in C#
- Bubble sort algorithm in C#
Heap Sort Algorithm Explanation
Heap sort algorithm is based on the principle of heap data structure. Once you have a good understanding of the heap data structure it will be very easy for you have a good grasp of this particular algorithm.
We have to start from the last sub tree and heapify it. As we can see from the above figure the leaf starts from the position 5. All the nodes before node 5 are not leaf.
We will start with node 4, and check if the element at node 4 i.e 0 is greater than both of its children i.e. elements at node 8 and 9. And as we can see it is not the case, element at node 9 is greater than element at node 4. We have to inter change the elements at node 4 and 9. below figure shows the max heap for the sub node starting from position 4.
Now we move to node 3 in the heap. The children of the node 3 are elements 2 and 7. Out of all these three elements 7 is largest. We replace 7 and 5.
The heap looks like as shown in the figure below after these two operations.
Now go to the element at node 2 from figure 1. The element is 6. And we need to convert this sub heap with elements 6, 3 and 8 into a max heap. And 8 is the highest of of these. We will replace 6 and 8 to make it a max heap. And the heap will look as shown in the figure below.
Finally we go to the node 1 of the heap. And we will compare both its children to check if it is a max heap or not. As we can see from the above figure, element at node 1 i.e. 9 is already greater than both of its children. Concluding that is already a max heap.
We have created a heap structure for the representation purpose. Originally we are working on the array. After all the above operations our array will look like as shown below figure derived from the above heap.
Below is the code to convert an array to max heap.
In the BuilMaxHeap method we are starting from the last node which is not a leaf. And create a max heap for the previous nodes.
public static void BuilMaxHeap(int[] arr){
int elementCount = arr.Length;
int leafStartPosition = ((int)Math.Round((decimal)elementCount/2)) + 1;
for (int i = leafStartPosition - 1; i >=1 ;i--){
Max_Heapify(arr, i);
}
}
private static void Max_Heapify(int[] arr, int pos){
int leftChild = 2*pos;
int rightChild = 2*pos + 1;
int largest;
if(leftChild <= arr.Length && arr[leftChild - 1] > arr[pos - 1])
largest = leftChild;
else
largest = pos;
if(rightChild < arr.Length && arr[rightChild - 1] > arr[largest - 1])
largest = rightChild;
if(largest != pos)
{
int temp = arr[pos - 1];
arr[pos -1] = arr[largest - 1];
arr[largest - 1] = temp;
Max_Heapify(arr, largest);
}
}Now we can get the largest element from the above array. The largest element will be present at position 0. Once we get the max element from the array. We will bring the last element from the heap and put it at zero position.
private static int Extract_Max(int[] arr){
if(arr.Length < 1){
return Int32.MinValue;
}
int max = arr[0];
arr[0] = arr[arr.Length - 1];
Array.Resize(ref arr, arr.Length - 1);
Max_Heapify(arr, 1);
return max;
}Time Complexity: Time complexity of Max_Heapify is O(Logn). Time complexity of BuilMaxHeap() is O(n) and overall time complexity of Heap Sort is O(nLogn).