# Heap Sort

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, &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);
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)`

### Time and Space Complexity of Radix Sort

Heap Sort is used when

1. Systems concerned with security and embedded systems such as Linux Kernel.
2. Want to extract smallest or largest from list of items without sorting the list

#### Selection Sort

Here, We will discuss about selection sort in C, their algorithm, implementation code in C,…

#### Merge Sort

Here, We will discuss about Merge Sort in C, their algorithm, implementation code in C,…

Here, We will discuss about Radix Sort in C, their algorithm, implementation code in C,…

#### Counting Sort

Here, We will discuss about Counting Sort in C, their algorithm, implementation code in C,…

#### Quick Sort

Here, We will discuss about Quick sort in C, their algorithm, implementation in C, time…

#### Bucket Sort

Here, We will discuss about Bucket Sort in C, their algorithm, implementation code in C,…

### Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 contribute@totheinnovation.com. See your articles on the main page and help other coders.😎

Scroll to Top