Heap Sort: Heap Sort is very useful and efficient sorting algorithm in data structure. We can say it is a comparison base sorting algorithm, similar sort where we will find the higher element and add it at the end. We just repeat same thing again and again. In heap sort, we use binary heap data structure.
What is Binary Heap
A Binary heap is nothing but it is a Complete Binary Tree. In this, elements are stored in a different order such that parent node element is either greater or smaller than the value of its children nodes which is called max heap or min heap respectively. Binary Heap can be implemented by array and linked list and as we said binary heap is the complete binary tree so array is preferred for implementation.
Pseudo-code of Heap Sort
First, call build max heap to set the heap initially
After the heap is created, take the root and add it as the last element of the heap
Decrease the size of the heap
Call max heapify function of index 0, i.e., the new root of the heap
Heap Sort Algorithm Dry Run
input:
0
1
2
3
4
23
10
16
11
20
The first step – we will make max heap with the help of function
0
1
2
3
4
23
20
16
11
10
For i=4
0
1
2
3
4
20
11
16
10
23
After i=3
0
1
2
3
4
16
11
10
20
23
After i=2
0
1
2
3
4
11
10
16
20
23
After i=1
0
1
2
3
4
10
11
16
20
23
After i=0
0
1
2
3
4
10
11
16
20
23
Heap Sort program in C-language
#include <stdio.h>
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void heapify(int array[], int n, int i) {
int max = i;
int left_Child = 2 * i + 1;
int right_Child = 2 * i + 2;
if (left_Child < n && array[left_Child] > array[max])
max = left_Child;
if (right_Child < n && array[right_Child] > array[max])
max = right_Child;
if (max != i) {
swap(&array[i], &array[max]);
heapify(array, n, max);
}
}
void heap_Sort(int array[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(array, n, i);
for (int i = n - 1; i >= 0; i--) {
swap(&array[0], &array[i]);
heapify(array, i, 0);
}
}
void display(int array[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", array[i]);
printf("\n");
}
int main() {
int array[] = {11, 34, 9, 5, 16, 10};
int n = sizeof(array) / sizeof(array[0]);
printf("Original array:\n");
display(array, n);
heap_Sort(array, n);
printf("Sorted array:\n");
display(array, n);
}
