# Heap Sort

Last updated on September 4th, 2023 at 09:43 pm

Here, We will discuss about Heap Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications.

### What is Heap Sort?

Heap Sort is a comparison-based sorting algorithm. This sorting algorithm has more favorable worst-case O(n log n) runtime.

Heap Sort is an in-place algorithm but is not a stable sort.

Heaps can be used in sorting an array. In max-heaps, the maximum element will always be at the root.

Heap Sort uses this property of heap to sort the array.

### Heap Sort Algorithm

1. The tree satisfies Max-Heap property, then the largest element is stored at the root node.
2. Swap: Remove the root element and put at the end of the array (nth position). Put the last item of the tree(heap) at the vacant place.
3. Remove: Reduce the size of the heap by 1.
4. Heapify: Heapify the root element again so that we have the largest element at root.
5. The process is repeated until all items of the list are sorted.

#### Program Code in C

``````#include<stdio.h>

//function to swap the position of two elements
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

void heapify(int arr[], int n, int i)
{
//find largest among root, left and right child
int largest = i;
int left = 2*i+1;
int right = 2*i+2;

if(left<n && arr[left]>arr[largest])
largest = left;

if(right<n && arr[right]>arr[largest])
largest = right;

//swap and continue heapifying if root is not largest
if(largest != i)
{
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}

//main function to do heap sort
void heapsort(int arr[], int n)
{
//build max-heap
for(int i=n/2-1; i>=0; i--)
heapify(arr, n, i);

//heap sort
for(int i=n-1; i>=0; i--)
{
swap(&arr[0], &arr[i]);

//heapify root element to get highest element at root again
heapify(arr, i, 0);
}
}

//print an array
void printarray(int arr[], int n)
{
for(int i=0; i<n; i++)
printf("%d ", arr[i]);
printf("\n");
}

//Driver code
int main()
{
int data[] = {8, 4, 7, 1, 3, 5};
int n = sizeof(data)/sizeof(data[0]);
heapsort(data, n);

printf("Sorted array : ");
printarray(data, n);
}```Code language: C++ (cpp)```

#### Output

``Sorted array : 1 3 4 5 7 8`Code language: PHP (php)`