Heap Sort Program in C

«
»

Heap Sort in C is a comparison-based efficient sorting algorithm. It is based on a Binary Heap data structure. To understand the heap sort, we first need to know some basic terminologies related to the heap sort.

Binary Tree

In a Binary tree data structure, every element contains at most two children. Given diagram shows the binary tree.
Heap Sort Program - Binary Tree Example

Complete Binary Tree

It is a type of binary tree in which all the levels are completely filled except the last level i.e. leaf node. The complete binary tree is filled from the left to right. Following is an example of the complete binary tree.
Heap Sort Program - Complete Binary Tree Example

Binary Heap

A binary heap is a complete binary tree in which the elements are stored in such a way that the parent node is greater or smaller than its children nodes. It is classified into two types: max-heap and min-heap.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Max Heap
In the max-heap, the parent node has a greater value than the children nodes.
Heap Sort Program - Max Heap Example

Min Heap
In the min heap, the parent node contains a smaller value than its children nodes.
Heap Sort Program - Min Heap Example

What is Heapify?
Heapify is the process to make the heap data structure using the binary tree. It is also used when the root node is deleted from the heap. It again rebuilds the tree which follows the condition of the heap.

Problem Description

Write a C program to sort the array using the heap sort and display the sorted array.

Problem Solution

There are some operations that are needed to implement the heap sort. Here we have an array of integers that is needed to sort. We will use an array-based representation of the binary heap. In this representation, if the parent node is stored at the index i then its left child will be at 2*i + 1 and right child at 2*i + 2.

Heap Sort Algorithm

Following are the steps that should follow to implement the heap sort.

  1. Build a binary heap.
  2. Start iterating from mid to the start of the binary heap array.
  3. On every iteration, swap the root node with the last leaf node.
  4. Remove the leaf node by putting it back at the end of the new sorted array.
  5. Again do the heapify operation and repeat the iteration from step 2.
  6. Exit
Program/Source Code

Here is the source code to implement heap sort in C. Heap is built using array representation. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * Heap Sort Program in C
  3.  */
  4.  
  5. #include<stdio.h>
  6.  
  7. // function prototyping
  8. void heapify(int*,int, int);
  9. void heapsort(int*, int);
  10. void print_array(int*, int);
  11.  
  12. int main()
  13. {
  14.     int arr[] = { 10, 30, 5, 63, 22, 12, 56, 33 };
  15.     int n = sizeof(arr) / sizeof(arr[0]);
  16.  
  17.     printf("\nArray before sorting:\n");
  18.     print_array(arr, n);
  19.  
  20.     heapsort(arr, n);
  21.  
  22.     printf("\n\nArray after sorting:\n");
  23.     print_array(arr, n);
  24.  
  25.     return 0;
  26. }
  27.  
  28. /* sorts the given array of n size */
  29. void heapsort(int* arr, int n)
  30. {
  31.     // build the binary max heap
  32.     for (int i = n / 2 - 1; i >= 0; i--)
  33.     {
  34.         heapify(arr, n, i);
  35.     }
  36.  
  37.     // sort the max heap
  38.     for (int i = n - 1; i >= 0; i--)
  39.     {
  40.         // swap the root node and the last leaf node
  41.         int temp = arr[i];
  42.         arr[i] = arr[0];
  43.         arr[0] = temp;
  44.  
  45.         // again heapify the max heap from the root 
  46.         heapify(arr, i, 0);
  47.     }
  48. }
  49.  
  50. /* heapify the subtree with root i */
  51. void heapify(int* arr, int n, int i)
  52. {
  53.     // store largest as the root element
  54.     int largest = i;
  55.  
  56.     int left = 2 * i + 1;
  57.     int right  = 2 * i + 2;
  58.  
  59.     // now check whether the right and left right is larger than the root or not
  60.     if (left < n && arr[left] > arr[largest])
  61.     {
  62.         largest = left;
  63.     }
  64.  
  65.     if (right < n && arr[right] > arr[largest])
  66.     {
  67.         largest = right;
  68.     }
  69.  
  70.     // if the root is smaller than the children then swap it with the largest children's value
  71.     if (largest != i)
  72.     {
  73.         int temp = arr[i];
  74.         arr[i] = arr[largest];
  75.         arr[largest] = temp;
  76.  
  77.         // again heapify that side of the heap where the root has gone
  78.         heapify(arr, n, largest);
  79.     }
  80. }
  81.  
  82. /* printf the array */
  83. void print_array(int* arr, int n)
  84. {
  85.     for (int i = 0; i < n; i++)
  86.     {
  87.         printf("%d  ", arr[i]);
  88.     }
  89. }
Program Explanation

Let’s understand the Heap Sort Program in C by the given steps:
1. Print the unsorted array.
2. Creating the binary heap of the array.
3. Start iteration from the last leaf node of the heap to the root node.
4. Each iteration swaps the root node with the last leaf node and then calls the heapify operation to rearrange the heap.
5. On heapify operation, swap the larger children element with the root node if the root is smaller than the child.
6. Print the sorted array.

advertisement
Working of Heap Sort in C

Now, let’s understand the working of the heap sort algorithm with the diagram.

Here we are performing basically two types of operations:

  1. Building the array-based max heap.
  2. Heapify the heap on every root and leaf node swapping.

Let’s take an example of an unsorted array that has 8 elements.

10 30 5 63 22 12 56 33

Step 1: Construct Max Heap from Given Array i.e. {10, 30, 5, 63, 22, 12, 56, 33}

Initially, we must construct the max heap from the given array of elements.
Heap Sort Algorithm Example

advertisement

Now the given array will be changed and it is max-heap. Now the array looks like this:

63 56 33 12 30 22 10 5

Step 2: Delete the root node (63) & perform heapify operation.

The task is to delete the root node which is 63. To delete this node, we have to swap this node with leaf node 10 and remove the leaf node. After swapping we have to perform a heapify operation again.

Heap Sort Algorithm Example -  Deleting Root Node 63

Now the array is changed, and 63 is stored at the end of the list.

56 33 12 30 22 10 5 63

Step 3: Delete the root node (56) & perform heapify operation.

Again, we have to delete the root element 56. To delete the root element, we have to swap the root with the leaf node having data 5. After deletion, we have to perform the heapify operation.

Heap Sort Algorithm Example -  Deleting Root Node 56

After swapping the root node and leaf node, the array of elements is changed:

33 30 12 5 22 10 56 63

Step 4: Delete the root node (33) & perform heapify operation.

Now, we have to delete the root node 33. To delete the root node, we have to perform a swapping operation between the root node and the leaf node 10.

Heap Sort Algorithm Example -  Deleting Root Node 33

Now the array with be changed after the deletion process:

30 22 12 5 10 33 56 63

Step 5: Delete the root node (30) & perform heapify operation.

In this step, we have to delete the root node with data 30. To delete the root node, we have to perform the swapping operation between the root node and leaf node having data 10.
Heap Sort Algorithm Example -  Deleting Root Node 30

After deletion of the root node and swapping, the array is changed:

22 10 12 5 30 33 56 63

Step 6: Delete the root node (22) and leaf node & perform swapping operation.

In this step, delete the root node. To delete the root node, we have to swap the root node with the last leaf node 5. After swapping the leaf node, we have to heapify the heap.

Heap Sort Algorithm Example

Now the array is changed after the deletion of the root and leaf node.

12 10 5 22 30 33 56 63

Step 7: Delete the root node (12) & perform swapping operation.

Now in this step, we have to delete the root node 12. To delete the root node, we have to swap it with leaf node 5. After swapping operations, we need to heapify the max heap.
Heap Sort Algorithm Example -  Deleting Root Node 12

Now the array is changed after the swapping operation:

10 5 12 22 30 33 56 63

Step 8: Delete the root node (10) & perform heapify.

In this step, we need to delete the root node 10. To delete the root node, we have to perform the swapping operation between the two root nodes and the leaf node 5. After swapping, we do heapify.

Heap Sort Algorithm Example -  Deleting Root Node 10

After removing the root node, the array is changed:

5 10 12 22 30 33 56 63

Step 9: Delete the root node.

In this step, we have to delete the root node. Since there is only one node that remains, after deleting it, the heap will be empty.

Null
 
heap after deleting 5

Now the final sorted array is given below.

5 10 12 22 30 33 56 63

Time Complexity: O(n logn)
Here the traversal occurs n time, where n is the size of the array. To sort each element we need to perform a heapify operation which takes log n time.
Best case = Avg case = Worst case = O(n logn)

Space Complexity: O(1)
Since we are not using extra space to sort the list using heap sort. So space is constant.

Run Time Testcases

In this case, we are performing heap sort operation. The given array has the values 10, 30, 5, 63, 22, 12, 56, and 33.

Array before sorting:
10  30  5  63  22  12  56  33
 
Array after sorting:
5  10  12  22  30  33  56  63

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.