In heap sort, we create a heap. Heap is a type of binary tree. There are two types of heap:

- Max-heap.
- Min-heap.

**Max-heap**

When the value at any node of tree is greater than that of its all children then the tree is called max-heap.

**Min-heap**

When the value at any node of tree is smaller than that of its all children then the tree is call min-heap.

In heap sort first step is to build a heap from an array. For that take an array and build a tree out of it. We will build max heap.

**Array**

16, 11, 29, 26, 20, 18, 38, 17, 15, 5, 19

- To build a max-heap you need to take (n-1) level and compare it with the n level which is leaf node.
- Elements at (n-1) level are 15, 19, 18, 38. Compare them with their child. Only 15 and 19 have a child. We get a new tree.

- Similarly root elements at 2nd level are compared with 3rd level.
- 26 is greater than 11 and 38 is greater than 29.

**We get a max-heap**

Now we will see how to remove root element to use this heap to sort our array.

**Array to be sorted**

16, 11, 29, 26, 20, 18, 38, 17, 15, 5, 19

**Max-heap**

**This max heap can be represented using an array given below**

38, 26, 29, 17, 20, 18, 16, 11, 15, 5, 19

**Now we need to remove the root element to get the maximum element from an array**

- Again build heap after removing the root.
- Now arrange 26, 29, 17, 20, 18, 16, 11, 15, 5, 19 to build max-heap.

Now again remove the root element and it would be our 2nd largest element.

By repeating these steps we can take out root elements and then we get a sorted array.

## Heap Sort Algorithm Implementation

To sort an array using **heap sort **we need to build a **max-heap**.

**Array to be sort**

int a[] = {10000, 16, 11, 29, 26, 20, 18, 38, 17, 15, 5, 19};

**Note:** Place an element of large value at 0th element. It would make our calculations easier.

**Create a max_heap() function**

In this function we take the length of the array as a **last **element. This helps to specify the limit of the heap. If we divide **last** by **2 **then we get the parent of the last element which is of our interest and is in the last level.

void max_heap(int a[], int last){
int i;
for(i=last/2; i>0; i--){
helper_maxheap(a, i, last);
}
}

Now all the elements at **index <= 5** have one or more child. So we need to run a for loop from** index = last/2 **to 1. In max-heap value at all the parents node must be greater than the value at children node.

**Call helper_maxheap() method to build max-heap**

- Get the first child of the parent using
child = parent*2;

- Check to see that the child exist in the array.
while(child<=last){
}

- Check to see weather the
** left child** is larger or** right child**. if((child+1)<=last && a[child+1]>a[child])
child++;

- Check if the
**larger child** is greater than the** parent**. If yes then swap. if(a[child]>a[parent]){
temp = a[child];
a[child] = a[parent];
a[parent] = temp;
}

- Now the current parent-child has been checked. Now make sure that the tree below the current node satisfy the heap.
parent = child;
child = parent*2;

**Complete code for helper_maxheap() function.**

void helper_maxheap(int a[], int parent, int last){
int child, temp;
child = parent*2;
while(child<=last){
if((child+1)<=last && a[child+1]>a[child])
child++;
if(a[child]>a[parent]){
temp = a[child];
a[child] = a[parent];
a[parent] = temp;
}
/* current parent-child is checked. Now let a child be parent and its children if exists
will be located at (parent*2) index
*/
parent = child;
// new child to be checked
child = parent*2;
}
}

Now we have an array which we want to sort.

int a[] = {1000, 16, 11, 29, 26, 20, 18, 38, 17, 15, 5, 19};

Create** heap_Sort()** function which will take array containing max-heap as an argument.

We will remove the largest element which is at 1st index of an array from our max-heap. We will swap the 1st element with the last element of max-heap.

- Swap the
** 1st **and **last **element.
- Decrement
**last **index.
- Call helper_maxheap() to heapify the max-heap.

void heap_Sort(int a[], int last){
int temp;
while(last>1){
temp = a[1];
a[1] = a[last];
a[last] = temp;
last--;
helper_maxheap(a, 1, last);
}
}

**Complete code for heap sort**

#include <stdio.h>
#include <string.h>
void max_heap(int[], int);
void helper_maxheap(int[], int, int);
void heap_Sort(int[], int);
void heapify(int[], int);
main()
{
int a[] = {1000, 16, 11, 29, 26, 20, 18, 38, 17, 15, 5, 19};
int i;
max_heap(a, 11);
for(i =1;i<=11;i++){
printf("%d, ", a[i]);
}
heap_Sort(a, 11);
printf("\n");
for(i =1;i<=11;i++){
printf("%d, ", a[i]);
}
}
void max_heap(int a[], int last){
int i;
for(i=last/2; i>0; i--){
helper_maxheap(a, i, last);
}
}
void helper_maxheap(int a[], int parent, int last){
int child, temp;
child = parent*2;
while(child<=last){
if((child+1)<=last && a[child+1]>a[child])
child++;
if(a[child]>a[parent]){
temp = a[child];
a[child] = a[parent];
a[parent] = temp;
}
parent = child;
// new child to be checked
child = parent*2;
}
}
void heap_Sort(int a[], int last){
int temp;
while(last>1){
temp = a[1];
a[1] = a[last];
a[last] = temp;
last--;
// heapify
helper_maxheap(a, 1, last);
}
}