How To Implement Heap Sort In C?

Computers are really good at sorting things. They can complete complex sorting tasks in no time. The only thing left for us is to tell them the method to be used for the given sorting task. This article will tell your computer systems how to use Heap sort in C to sort your data.

This article will focus on following pointers,

• Fundamentals of Binary Heap
• Understanding the Algorithm with example
• Write a program for Heap sort in C
• Time Complexit

So let us get started with this Heap sort in C article,

At present, there are 100’s of well-known sorting algorithms present, and if you’re not satisfied with them you can prepare your own algorithm with enough knowledge of Data Structures, Algorithms and sorting. In this post, we will learn about the Heap Sort which is a widely used and based on Binary heap data structure. 

Fundamentals of Binary Heap

Apart from sorting application Binary Heap has other applications too such as Priority Queue, Graph Algorithms, etc. Binary Heap is a tree-like structure consisting of parent nodes and child nodes. Based on the relationship between the parent node and the child node it can be further classified as

1. Min Heap
2. Max Heap

Heap sort in C: Min Heap

Min Heap is a tree in which the value of parent nodes is the child nodes. For example let’s consider an array- [5, 6, 11, 4, 14, 12, 2]. The image above is the min heap representation of the given array.

Heap sort in C: Max Heap

Max heap is opposite of min heap in terms of the relationship between parent nodes and children nodes. Here, the value of parent node children nodes. Let’s consider the same array [5, 6, 11, 4, 14, 12, 2]

The image above is the Max heap representation of the given array. Now, we fundamentally know what Binary Heaps are and their types. These concepts will greatly help us while understanding the Heap Sort Algorithm.

Let us continue with this article on Heap sort in C,

Understanding the Algorithm with Example

Before writing the program we shall understand the approach we will be using to sort the given array. First, we will discuss the algorithm after that we will understand it with an example. We will be using max heap for our use case.

1. Initially, we will ask the user to enter that is to be sorted.
2. Once, the array is received we need to create a heap of the numbers received from the array to sort them in ascending order.
3.  Now, we need to create a max heap out of that heap. There’s one rule that has to be followed to create a max heap, i.e the value of the parent node should be the value of its children nodes.
4. After the tree is created we need to check for the above condition. If, the value of the child node is greater than the parent node we need to swap their values and check once again until the condition mentioned in step 3 is specified.
5. Once the condition is satisfied and all the elements are arranged accordingly. We need to swap the root node with the last node.
6. After swapping, remove the last node from the heap. We are removing it as it has been sorted.
7. Repeat steps 4, 5, and 6 until there’s one element left in the heap.

Understanding the above Algorithm with an example will give you an in-depth understanding of the whole process. We will be using the same array which we used above to make things more relatable.

Example array = [5, 6, 11, 4, 14, 12, 2]

Yes, the exmple we considered is a big one but let’s understand what’s happening when it comes to implementing Heap sort in C or in other in language,

1. In the first step, we started making a heap, as 11 is greater than 5 we swapped them to create a max heap
2. Then we introduced other members of the array and swapped 6 with 14 to create a max heap
3. In step 4 and 5 we swapped 15 with 11 and 12 with 5 respectively.
4. In step 5 our max heap is created.
5. We swapped 14 with 2 in step 6 as we had discussed in our previous section that once max heap is created we need to swap the first node with the last node and remove the last node hence we removed 14
6. To create the max heap again we swapped 5 with 2
7. After the creation of max heap, we swapped 2 with 12 and removed 12
8. Again to create a max heap we swapped 11 with 2 and 6 with 2 after that we swapped 11 and 2 as max heap was created and removed 11
9. In step 12 and 13 we swap 6 with 2 and 4 with 2 respectively
10.  As we have a max heap we swap 6 with 2 and remove 6

At this point, you’ll notice that the numbers are being removed in ascending order and are placed in the array from right to left

1. In step 15 we swap 5 with 2 to create a max heap and again swap 2 with 5 and remove 5
2. Once we swap 2 with 4 to create max heap and again swap 4 with 2 to remove 4, we are almost done.
3. Finally, we are left with 1 element in our heap, i.e 2.
4. That element is placed in the 0th position of the array and the algorithm is completed.

Let us now go ahead with the programming part,

Write a Program for Heap sort in C

Now, we have a good understanding of the sorting algorithm that we will be using. So, Let’s get started.

#include<stdio.h>
#include <conio.h>
void Adjust(int Heap_of_Numbers[],int i)&nbsp; /*Function to arrange the elements in the heap*/
{
int j;
int copy;
int Number;
int Reference = 1;
Number=Heap_of_Numbers[0];
while(2*i<=Number && Reference==1)
{
j=2*i;&nbsp; &nbsp;
if(j+1<=Number && Heap_of_Numbers[j+1] > Heap_of_Numbers[j])
j=j+1;
if( Heap_of_Numbers[j] < Heap_of_Numbers[i])
Reference=0;
else
{
copy=Heap_of_Numbers[i];
Heap_of_Numbers[i]=Heap_of_Numbers[j];
Heap_of_Numbers[j]=copy;
i=j;
}
}
}
void Make_Heap(int heap[])
{
int i;
int Number_of_Elements;
Number_of_Elements=heap[0];
for(i=Number_of_Elements/2;i>=1;i--)
Adjust(heap,i);
}
int main()
{
int heap[30];
int NumberofElements;
int i;
int LastElement;
int CopyVariable;
printf("Enter the number of elements present in the unsorted Array:");
scanf("%d",&NumberofElements);
printf("nEnter the members of the array one by one:"); /* Asking for the elements of the unsorted array*/
for(i=1;i<=NumberofElements;i++)
scanf("%d",&heap[i]);
heap[0]=NumberofElements;
Make_Heap(heap);
while(heap[0] > 1) /*Loop for the Sorting process*/
{
LastElement=heap[0];
CopyVariable=heap[1];
heap[1]=heap[LastElement];
heap[LastElement]=CopyVariable;
heap[0]--;
Adjust(heap,1);
}
printf("nSorted Array:n");/*Printing the sorted Array*/
for(i=1;i<=NumberofElements;i++)
printf("%d ",heap[i]);
return 0;
}

I’ve used the same array to verify our results and as you can see from the output window, we received the same result. Doing manually involved many steps and there’s a possibility of errors hence this program can help us to solve those problems and save our time.Output

This brings us to the final bit of this Heap sort in C article,

Heap sort in C: Time Complexity

Now, that we have understood all the key concepts we need to check the most important aspect of any algorithm i.e its time complexity. For the people who aren’t aware of this term here’s a quick explanation. Time complexity is a measure of time taken by an algorithm to compute the output.

The time complexity of Heap Sort is O(nLogn).

With this we come to the end of this article on ‘Heap sort in C’. I hope you found this informative and helpful, stay tuned for more tutorials on similar topics.

Got a question for us? Mention them in the comments section of  this article and we will get back to you.