Heap Sort in C Programming

In this source code example, we will write a code to implement the Heap Sort algorithm in the C programming language.

Let's write a C program to sort N numbers in ascending order using the Heap Sort algorithm:

Heap Sort in C Programming

In this C program, we will take input from the User or console. 
#include<stdio.h>

void Heapsort(int[], int);
int Parent(int);
int Left(int);
int Right(int);
void Heapify(int[], int, int);
void Buildheap(int[], int);

void main() {
	int x[20], i, n;
	printf("\n Enter the no of element to be sorted:");
	scanf("%d", &n);
	printf("\n Enter %d elements:", n);
	for (i = 0; i < n; i++)
		scanf("%d", &x[i]);
	Heapsort(x, n);
	printf("\n The sorted array is:\n");
	for (i = 0; i < n; i++)
		printf("%4d", x[i]);
}

int Parent(int i) {
	return (i / 2);
}
int Left(int i) {
	return (2 * i + 1);
}
int Right(int i) {
	return (2 * i + 2);
}

void Heapify(int a[], int i, int n) {
	int l, r, large, temp;
	l = Left(i);
	r = Right(i);
	if ((l <= n - 1) && (a[l] > a[i]))
		large = l;
	else
		large = i;
	if ((r <= n - 1) && (a[r] > a[large]))
		large = r;
	if (large != i) {
		temp = a[i];
		a[i] = a[large];
		a[large] = temp;
		Heapify(a, large, n);
	}
}

void Buildheap(int a[], int n) {
	int i;
	for (i = (n - 1) / 2; i >= 0; i--)
		Heapify(a, i, n);
}

void Heapsort(int a[], int n) {
	int i, m, temp;
	Buildheap(a, n);
	m = n;
	for (i = n - 1; i >= 1; i--) {
		temp = a[0];
		a[0] = a[i];
		a[i] = temp;
		m = m - 1;
		Heapify(a, 0, m);
	}
}

Output:

Enter the no of element to be sorted: 5

Enter 5 elements: 20 10 30 50 40

The sorted array is: 10 20 30 40 50

Related Algorithms in C Programming