Heap Sort in C

When we deal with a large set of data, we want to organize it in a specific order so that whenever we want to search for a particular item, we could find it in no time. For this, we have sorting algorithms, like the heap sort.

Sorting algorithms help us to arrange the elements in a specific order so that our searching algorithms can deliver better performance. There are many basic sorting algorithms we have in common with Data Structure & Algorithms , and one of the famous among the same is heap sort.

Here in this article, we have provided a brief explanation of what is heap sort, how it works, and how to implement it in the C language. Before we discuss what heap sort is and its algorithm, let us have a look at the terminology we use with the sorting algorithm.

What is Tree?

A tree is a non-primitive, non-linear data structure that forms a hierarchical model.

Tree Level

The level of a tree signifies the height of the tree. The root node lay on the top level, which is level 0. As we go down with a tree, the level increases.

Binary Tree

A binary tree is a tree data structure where each node can have a maximum of 2 child nodes.

Complete Binary Tree

A binary tree in which every level, except possibly the last, is filled, and all nodes are as far left as possible is a complete binary tree.

Heap Data Structure

A complete binary tree, with a condition, either each parent node is higher than its child node, or each parent node is smaller than its child node.

Types of Heap:

• Min Heap - If the parent node is smaller than the child node, it would be called a Min heap.
• Max Heap - In a heap, if each parent node is higher than its child node, then it would be termed as a Max heap.

Relation of Arrays with Complete Binary Tree

When we say sorting using heap sort, we mean to sort the elements of the array using the tree data structure. Hence, there is a relation between the arrays index and binary tree levels. We can implement an array using a binary tree. For example: Arr =[ 100,200,300,400,500,600]

                       100
                     /      \
                    /        \
                  200         300
                /     \       /     
               /       \     /
             400      500   600

The first element of the array would be the root node element of the tree, and we will start to fill all the elements of an array from left to right in the binary tee. The left child of the ith index element would be at (2*i+1) index and the right child at (2*i+2) index.

What is a Heap Sort?

Like selection sort , heap sort also applies the divide and conquer algorithm. It creates the subarrays and compares them to form a specific order, which could be ascending or descending.

In heap sort, we use a heap tree data structure to hold the elements of the array. While using the heap tree, we compare the child element with its parent element and swap if necessary.

With heap sorting, we have 2 options, whether to use the max heap structure or the min heap structure.

In max heap, we try to pull the largest element on the root node. In min heap, we try to remove the smallest element on the root node. We can find the element for the first and the last index values in either way. Often, we use the max heap structure for implementing the heap sort.

Heapify The Tree

Heapify is the crucial procedure in a heap sort. In heapify, we use recursion and try to make a max heap structure of each node with its child node. In heapify, we treat the array as a heap tree, where each node has two child nodes, which lay at (i*2+1) and (i*2+2) indices, and we try to make them a max heap tree.

Heap Sort Complexity

Heap Working

• Treat the array as a heap tree, where each element child nodes lay on (2*i+1) and (2*i+2) indices.
• Use the heapify function to create the max heap of each sub-tree, and repeatedly remove the largest element from the heap and insert it into the array.

Heap Sort in C Program

#include<stdio.h>
#include <conio.h>
void heapify_function(int arr[])
{
    int i,n;
    n=arr[0];
    for(i=n/2;i>=1;i--)
    adjust(arr,i);
}
void adjust(int arr[],int i)
{
    int j,temp,n,k=1;
    n=arr[0];
    while(2*i<=n && k==1)
    {
       j=2*i;
       if(j+1<=n && arr[j+1] > arr[j])
           j=j+1;

       if( arr[j] < arr[i])
           k=0;
       else
       {
           temp=arr[i];
           arr[i]=arr[j];
           arr[j]=temp;
           i=j;
        }
      }
}

void main()
{
int arr[100],n,temp,last,i;
clrscr();
printf("How many Numbers you want to enter in your array: \n");
scanf("%d",&n);
printf("Enter Elements in array:\n");
for(i=1;i<=n;i++)
scanf("%d",&arr[i]);
arr[0]=n;
heapify_function(arr);
while(arr[0] > 1)
{
    last=arr[0];
    temp=arr[1];
    arr[1]=arr[last];
    arr[last]=temp;
    arr[0]--;
    adjust(arr,1);
}

printf("Array After Heap Sort\n");
for(i=1;i<=n;i++)
printf("%d ",arr[i]);
getch();
}

Sample Output:

How many Numbers you want to enter in your array:

10

Enter Elements in array:

16
21
40
3
2
5
9
18
17
16
Array After Heap Sort
2 3 5 9 16 16 17 18 21 40

Advantages of Heap Sort

• Has a logarithmic time complexity.
• Always suggested for huge arrays.
• It is an in-place sorting algorithm that does not require extra memory space for an additional array.
• The same time complexity for average, best, and worst cases.

Disadvantages of Heap Sort

• It is not a stable algorithm, which means the order of the same element may be changed.
• Not that much efficient as compared to quick and merge sorting algorithms.
• The recursive call can be complicated.

Conclusion

That sums up this article on heap sort in C. Heap sort does not have that much application in the real world because we have better sorting algorithms, namely quick sort and merge sort . In Priority Queues implementation, however, we often use heap sort. Linux kernel also uses it.

To understand the C language in-depth, you can buy this course .

People are also reading:

• Recursive Bubble Sort in C
• Quick Sort in C
• Bubble Sort in C
• What is Shell Sort?
• Counting Sort in C
• C Program to Extract a Portion of String
• Binary Search in C
• What is the Radix Sort?
• Stack vs Heap