Home » C/C++ Data Structure programs

# C program to implement Heap Sort Algorithm

**Heap Sort Algorithm**: Here, we are going to learn about the heap sort algorithm, how it works, and c language implementation of the heap sort.

Submitted by Sneha Dujaniya, on June 19, 2020

**Heap Sort** is a comparison-based sorting algorithm that makes use of a different data structure called Binary Heaps. Let us understand some important terms,

**Complete Binary Tree**: A tree is complete when all the levels (except of course the last level) are completely filled, i.e. all the parent nodes have two children nodes each and all the nodes are as far left as possible which means first we fill the left node and then the right.-
**Binary Heap**: It is a complete binary tree but there is an order of elements from parent to children in Binary Heap. They can be of two types,**Max Binary Heap or Max Heap**where the parent node is greater than its two children nodes.**Min Binary Heap or Min Heap**where the parent node is smaller than its children nodes.

The *main()* function of **Heap Sort** is to call the *heapify()* function which leads to the building of a max heap and then the largest element is stored in the last position of the array as so on till only one element is left in the heap. Array representation of heap is preferred because it occupies less space and also it is easy to reference the root and children nodes.

**Algorithm (Considering Max heap):**

- First, we form a Max Heap such that the first node or the root node is the largest element. This step takes
**O(N)**time complexity. - Next, we swap the root element with the last element of the heap and reduce the size of heap by 1.
- Repeat steps 1 and 2 are till only 1 element is left.

**How to build the Heap?**

The *heapify* procedure can be applied to a node only when its children nodes are *heapified*. Therefore, we start the *heapification* with the last non-leaf node. To find the first non-leaf node, the following formula is used: **First non-leafy node = lower bound (n/2)**

Hence, if there are 5 elements in the heap, the first non-leafy node would be the second node or the node at index 1.

**Pseudo Code:**

Heap_Sort (arr[], n) { // Creating the initial Max heap for i = n/2 – 1 to 0: heapify(arr, n, i) // Swapping largest element and repeating the steps further for i = n-1 to 0: swap(arr[0], arr[i] heapify(arr, n, i) } Heapify (arr[], n, i) { int largest = i; int left = 2*i + 1; // Left child int right = 2*i + 2; // Right child // Check if left child exists and is larger than root If (left < n && arr[left] > arr[largest]): Largest = left; // Check if right child exists and is larger than largest If (right < n && arr[right] > arr[largest]): largest = right; // Change root, if root is not the largest If(largest != i) Swap(arr[i], arr[largest]) Heapify(arr, n, largest); //Repeat till max heap is obtained }

**Time Complexity:**

The time complexity of Heap sort is:

- Worst Case = O(N log N)
- Average Case = Ɵ(N log N)
- Best Case = Ω(N log N)
- Space Complexity: Ɵ(1)

The time complexity of Heapify is O(log N) and that of Build_heap / Heap_Sort is O(N). The overall complexity of Heap_Sort is therefor, O(N log N).

**Heap Sort Implementation:**

#include <stdio.h> void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void heapify(int arr[], int n, int i) { int left, right, largest; largest = i; left = 2 * i + 1; right = 2 * i + 2; // Check if left child exists and is larger than its parent if (left < n && arr[left] > arr[largest]) largest = left; // Check if right child exists and larger than its parent if (right < n && arr[right] > arr[largest]) largest = right; // if root is not the largest if (largest != i) { swap(&arr[i], &arr[largest]); //make root the largest heapify(arr, n, largest); // Apply heapify to the largest node } } void heap_sort(int arr[], int n) { int i; for (i = (n / 2) - 1; i >= 0; i--) heapify(arr, n, i); for (i = n - 1; i >= 0; i--) { swap(&arr[0], &arr[i]); //Move the largest element at root to the end heapify(arr, i, 0); //Apply heapify to reduced heap } } int main() { int arr[] = { 20, 13, 34, 56, 12, 10 }; int n = sizeof(arr) / sizeof(arr[0]); printf("Array:\n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); heap_sort(arr, n); printf("\nAfter performing Heap Sort:\n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; }

**Output:**

Array: 20 13 34 56 12 10 After performing Heap Sort: 10 12 13 20 34 56

**Applications:**

**Job Scheduling**: In Linux OS is used due to low space and time complexity**Graph Algorithms**: Djikstar's Algorithm, Prim's Algorithm and Huffman Coding

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.