# Heap Sort Algorithm C Program

## C Program For Heap Sort Algorithm using Heapify

Learn how to implement Heap Sort Algorithm in C Programming Language. The heap sort in data structure can be solved by using Heapify or with Linked Lists. Here, we have demonstrated algorithm for heap sort in c using heapify technique.

#### What is Heap Sorting 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 maximum number of nodes except possibly the last level since all the last level nodes occur to the left.

**Must Read: C Program For Quick Sort Algorithm**

The Heap Sort Program is performed in two phases:

- Building a Max Heap from the given elements stored in the array.
- Continuously deleting the root node till 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.

**Must Read: C Program To Implement Dijkstra’s Algorithm**

#### C Program For Heap Sort Algorithm using Heapify (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"); } |

**Must Read: C Program For Depth First Search Algorithm**

#### Heap Sort Algorithm 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 sorting algorithm is **O(1)**. This algorithm is preferable for larger lists. The average case complexity, worst case complexity and best case complexity of heap sort program is **O(n log n)**.

#### Output

If you have any compilation errors or doubts about Heap Sort Algorithm in C Programming, 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.