# Heap Sort Program in C

## Heap Sort in C

A heap is a complete binary tree which is represented using array or sequential representation.

It is a special balanced  binary tree data structure where root node is compared with its children and arranged accordingly.Normally in max heap parent node is always has a value greater  then child node.

The  worst and  Average complexity of heap sort is O(n log2 n).

• From the given array, build the initial max heap.
• Interchange the root element with the last element.
• Use repetitive downward operation from root node to rebuild the heap of size one less than the starting. ### Algorithm of Heap Sort

MAX-HEAPIFY(A,i)
1- i<-left[i]
2- r<-right[i]
3- if l<heap-size[A]and A[l]>A[i]
4- then largest<-1
5- else largest<-i
6- if r<heap-size[A] and A[r]>A[largest]
7- then largest<-r
8- if largest!=i
9- then exchange A[i]<->A[largest]
10- MAX-HEAPIFY[A,largest]

HEAP-SORT(A)
1- BUILD-MAX-HEAP(A)
2- for i<-length[A] down to 2
3- do exchange A<-> heap-size[A]-1
4- heap-size[A]<-heap-size[A]-1
5- MAX-HEAPIFY(A,1)

BUILD-MAX-HEAP(A)
1- heap-size[A]<-length[A]
2- for i<-(length[A]/2) down to 1 do
3- MAX-HEAPIFY(A,i)

## Implementation of Heap Sort

As we know that heap sort is based on the tree structure.

so we will take an example of heap sort with the based on tree.

Originally the given array is :[6,14,3,25,2,10,20,7,6]

First we call Build-max heap

heap size[A]=9

so,i=4 to 1, call MAX HEAPIFY (A,i)

i.e., first we call MAX HEAPIFY (A,4)

A[l]=7, A[i]=A = 25,A[r] = 6

l<- left = 8

r<-right = 9

8<9 and 7>25 (false)

Then,largest <-4

9<9 and 6>25(false)

Then,largest = 4

A[i]<-> A

Now call MAX HEAPIFY (A,2)  the A[length] =9

So, i=A/2 = 9/2 =4

i=4

since the parent node is greater than its child node.

If it is parent node is greater than child node then the parent node replace with the lesser child node.

similarly for i=3,2,1 we get the following heap tree.  Now call MAX HEAPIFY

Now we will replace the root node to last child In this photo is shown by replace 25 to 6.

Now call MAX HEAPIFY

Now we will replace the root node to last child In this photo is shown by replace 20 to 6. Again call MAX HEAPIFY,

we get exchange A and A which is shown by a image. Again call MAX HEAPIFY,

we get exchange A and A which is shown by a image. Similarly,call MAX HEAPIFY

we’ll interchange A and A. which is shown by this image. Similarly,call MAX HEAPIFY

we’ll interchange A and A. which is shown by this image.  Similarly,call MAX HEAPIFY

we’ll interchange A and A. which is shown by this image.

Final,call MAX HEAPIFY

we’ll interchange A and A. which is shown by this image.

and finally array will be sorted.

### C Code of  Heap Sort

`#include<stdio.h> // including library files int temp;void heapify(int arr[], int size, int i)//declaring functions { int max = i; int left = 2*i + 1; int right = 2*i + 2;if (left < size && arr[left] >arr[max]) max= left;if (right < size && arr[right] > arr[max]) max= right;if (max!= i) { // performing sorting logic by using temporary variable temp = arr[i]; arr[i]= arr[max]; arr[max] = temp; heapify(arr, size, max); } }void heapSort(int arr[], int size)// providing definition to heap sort{ int i; for (i = size / 2 - 1; i >= 0; i--) heapify(arr, size, i); for (i=size-1; i>=0; i--) { // swaping logictemp = arr; arr= arr[i]; arr[i] = temp; heapify(arr, i, 0); } }void main() // defining main() { int arr[] = {58, 134, 3, 67, 32, 89, 15, 10,78, 9};// array initializing with their elements. int i; int size = sizeof(arr)/sizeof(arr);heapSort(arr, size);printf("printing sorted elements\n"); // printing the sorted array for (i=0; i<size; ++i) printf("%d\n",arr[i]); }`

#### Output

printing sorted elements

3
9
10
15
32
58
67
78
89
134

## Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews. 