In this tutorial you will learn about the C Program to implement HEAP sort Algorithm and its application with practical example.
C Program to implement HEAP Sort Algorithm
In this tutorial, we will learn to create a C program that will do HEAP sorting using C programming.
Prerequisites
Before starting with this tutorial we assume that you are best aware of the following C programming topics:
- Operators in C Programming.
- Basic Input and Output function in C Programming.
- Basic C programming.
- For loop in C Programming.
- Creating and Using the user-defined function in C programming.
What is Heap Sort?
In every programming language, the sorting of data is a very important factor. In C Language. Many different techniques for sorting are available to work with but in this tutorial, we will focus on the Heap Sort Technique.
This technique is opposite to the selection sort technique. Here, we will select the highest value and put it in last, and create a heap for maximum values. This processing is continued till the smallest value is found.
Algorithm
Heap Sort
|
1 2 3 4 5 6 7 |
HeapSort(arry) MaxiHeap(arry) for i = length(arry) to 2 swap arry[1] with arr[i] heap_size[arry] = heap_size[arry] ? 1 MaxiHeapify(arry,1) End |
MaxiHeap (arry)
|
1 2 3 4 5 |
BuildMaxHeap(arry) heap_size(arry) = length(arry) for i = length(arry)/2 to 1 MaxHeapify(arry,i) End |
MaxiHeapify(arry,i)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
MaxHeapify(arry,i) l = left(i) r = right(i) if l ? heap_size[arry] and arry[l] > arry[i] largest = l else largest = i if r ? heap_size[arry] and arry[r] > arry[largest] largest = r if largest != i swap arry[i] with arry[largest] MaxHeapify(arry,largest) End |
Program For Heap Sort
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <stdio.h> /* function for heapifing a subtree. Here 'i' is the index for the root node in array x[], ,'no' is the size of heap. */ void heapify(int x[], int no, int i) { int largest = i; // As a root Initialization of largest int left = 2 * i + 1; // The left child int right = 2 * i + 2; // The right child // The left child is larger than root if (left < no && x[left] > x[largest]) largest = left; // The right child is larger than root if (right < no && x[right] > x[largest]) largest = right; // The root is not largest if (largest != i) { // swap x[i] with x[largest] int flag = x[i]; x[i] = x[largest]; x[largest] = flag; heapify(x, no, largest); } } /*Function for implementing the heap sort algo*/ void heapSort(int x[], int no) { for (int i = no / 2 - 1; i >= 0; i--) heapify(x, no, i); // One by one extract an element from heap for (int i = no - 1; i >= 0; i--) { /* Move current root element to end*/ // swap x[0] with x[i] int flag = x[0]; x[0] = x[i]; x[i] = flag; heapify(x, i, 0); } } /* function to print the array elements */ void printArr(int arr[], int no) { for (int i = 0; i < no; ++i) { printf("%d", arr[i]); printf(" "); } } int main() { int x[] = { 9, 8, 35, 89, 69, 59, 47, 84, 79}; int no = sizeof(x) / sizeof(x[0]); printf("Elements of array before sorting are - \n"); printArr(x, no); heapSort(x, no); printf("\nElements of array after sorting are - \n"); printArr(x, no); return 0; } |
Output:-
In the above program, we have first declared and initialized a set of variables required in the program.
- n = it will hold the size of the array.
- arr[] = it will hold the value of the array.
- x[]= it will hold the elements in an array.
Function to print array:-
Function For Heaping
HEAP sort function
Main function body
