# 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,

1. 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.
2. 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,
1. Max Binary Heap or Max Heap where the parent node is greater than its two children nodes.
2. 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):

1. 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.
2. Next, we swap the root element with the last element of the heap and reduce the size of heap by 1.
3. 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, 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:

1. Worst Case = O(N log N)
2. Average Case = Ɵ(N log N)
3. Best Case = Ω(N log N)
4. 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, &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);

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:

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