Learn how to implement Heap Sort Program in C using Array data structure. The heap sort algorithm in C programming can be implemented using Heapify or with Linked Lists.
What is Heap Sort Algorithm?
A Heap is a binary tree that satisfies the two properties:
- Heap Order Property: The key value in every node must be greater than or equal to the key values in both its child nodes.
- Structure Property: All the levels have a maximum number of nodes except possibly the last level since all the last level nodes occur to the left.
The Heap Sort algorithm is performed in 2 phases:
- Building a Max Heap from the given elements stored in the array.
- Continuously deleting the root node until there is only one element/node left in the tree.
The root node of the heap always has the largest element. If we successively delete the root node, elements can be fetched in descending order by deleting them one by one. Now, these deleted elements can be stored in a separate array.
Note: This Heap Sort Program in C is compiled with GNU GCC Compiler and developed using gEdit Editor and Terminal in Linux Ubuntu Operating System.
Heap Sort Program in C using Arrays
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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #include <stdio.h> #define MAX 100 void heap_sorting(int elements[], int limit); void show(int elements[], int limit); void restoring(int elements[], int count, int limit); int delete_root(int elements[], int *limit); void heap_builder(int elements[], int limit); int main() { int count; int elements[MAX], limit; printf("\nEnter Total Number of Elements:\t"); scanf("%d", &limit); for(count = 1; count <= limit; count++) { printf("Element No.%d:\t", count); scanf("%d", &elements[count]); } printf("\nElements To Sort\n"); show(elements, limit); heap_sorting(elements, limit); printf("\nSorted Elements List\n"); show(elements, limit); return 0; } void heap_sorting(int elements[], int limit) { int temp; heap_builder(elements, limit); printf("\nHeap Elements\n"); show(elements, limit); while(limit > 1) { temp = delete_root(elements, &limit); elements[limit + 1] = temp; } } void heap_builder(int elements[], int limit) { int count; for(count = limit / 2; count >= 1; count--) { restoring(elements, count, limit); } } int delete_root(int elements[], int *limit) { int temp = elements[1]; elements[1] = elements[*limit]; (*limit)--; restoring(elements, 1, *limit); return temp; } void restoring(int elements[], int count, int limit) { int left_child = 2 * count, right_child = left_child + 1; int num = elements[count]; while(right_child <= limit) { if(num >= elements[left_child] && num >= elements[right_child]) { elements[count] = num; return; } else if(elements[left_child] > elements[right_child]) { elements[count] = elements[left_child]; count = left_child; } else { elements[count] = elements[right_child]; count = right_child; } left_child = 2 * count; right_child = left_child + 1; } if(left_child == limit && num < elements[left_child]) { elements[count] = elements[left_child]; count = left_child; } elements[count] = num; } void show(int elements[], int limit) { int count; for(count = 1; count <= limit; count++) { printf("%3d", elements[count]); } printf("\n"); } |
Heap Sort Algorithm Analysis
Here’s the heap sort time complexity analysis. The first phase of this algorithm has a running time of O(n). However, the delete of the nodes takes O(log n) time, making the complexity of the second phase as O(n log n).
Heap Sort is a stable sort and it is an in-place sorting algorithm. The space complexity of the heap sort algorithm is O(1). This algorithm is preferable for larger lists. The average case complexity, worst-case complexity, and best case complexity of this algorithm is O(n log n).
Output
If you have any compilation errors or doubts about Heap Sort Program in C, let us know about it in the comment section below.
I believe Heap Sort algorithm is the fastest of all the other sorting algorithms, Isn’t it?
I think understanding binary trees is a prerequisite for this sorting algorithm.
I want Linked List implementation of Heap Trees. Please upload it asap.