In this tutorial, we will write a C program to implement heap sort. Before that, you may go through the following topics in C.
Heap Sort Algorithm
Heap is a tree in heap sorting that possesses some specific properties whose value should be greater than or equal to that of the children node.
Heapsort is a comparison-based sorting algorithm and is also considered as the improved Selection sort. It is based on a Binary Heap data structure so to understand we must know two types of data structure:
Arrays and trees
Learn more on Heap sort.
Implementation of HeapSort Algorithm in C
Question: C program to implement Heap sort using function.
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | // implementation of heap sort in C program #include <stdio.h> //function prototype void heapSort(int arr[], int n); void heapify(int arr[], int size, int i); //main function int main() { int arr[30], n, i; printf("Enter the number of elements: "); scanf("%d", &n); printf("Enter %d Elements:\n", n); for (i = 0; i < n; i++) scanf("%d", &arr[i]); //calling sorting function heapSort(arr, n); //Display the result printf("\nArray after sorting: \n"); for (i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } void heapSort(int arr[], int n) { // create heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i = n - 1; i > 0; i--) { // arrA[0] being max element int x = arr[0]; arr[0] = arr[i]; arr[i] = x; // call max heapify(arr, i, 0); } } void heapify(int arr[], int size, int i) { int largest = i; // root //Indexes int leftChild = 2 *i + 1; int rightChild = 2 *i + 2; // If left child is larger than root if (leftChild < size && arr[leftChild] > arr[largest]) largest = leftChild; // If right child is larger than root if (rightChild < size && arr[rightChild] > arr[largest]) largest = rightChild; // If root is not largest if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // Recursive call heapify(arr, size, largest); } } |
Output:
Enter the number of elements: 6
Enter 6 Elements:
25
98
3
124
66
9
Array after sorting:
3 9 25 66 98 124