Heap Sort Program in C, C++, Java with Examples | FACE Prep

In this article, we will be discussing Heap Sort program in C, C++ and Java with examples. Heap sort algorithm implementation, Heap sort pseudocode, time complexity, etc are also discussed in this article.

Prerequisites: Merge Sort, Insertion Sort

What is Heap Sort Algorithm?

Before we get into Heap sort, let’s understand what a Heap data structure is.

Heap is a special kind of binary tree in which elements are stored in a hierarchical manner. Heap has some additional rules – it must always have a heap structure, where all the levels of the binary tree are filled up from left to right. Second, it must either be ordered as a max heap or a min-heap.

  • Max heap – Parent node is greater than or equal to the value of its children node
  • Min heap – Parent node is less than or equal to the value of its children node

In Heap sort, we will be dealing with Max heap. Using max heaps, we can sort an unsorted array of elements. In simple, this is how it works

heap sort in c

Heap Sort Example 

Let’s see how sorting takes place with the help of heap. Consider an array arr[] = {4, 3, 7, 1, 8, 5}

1) Firstly, let’s convert the given array to a binary tree. The representation of a binary tree for the given array looks as shown below.

heap sort program in c

2) Next, build max-heap from the above tree. A max tree is where all the parent nodes are of higher value than the children nodes.

heap sort program in c

3) Now, swap the root node with the last element of the heap node. This means largest value has moved to its correct position. So, remove the largest value from the tree. After removing, the tree looks as shown below.

heat sort program in c

4) Repeat step 3 until no elements are left in the heap

heap sort program in c

heap sort program in c

heap sort program in c

heap sort program in c

heap sort algorithm in c

Heap Sort Program in C, C++, Java

Here is the implementation of Heap sort in various languages.

#include
int temp;
void swap_largest(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int left = 2*i + 1;
int right = 2*i + 2;

// If left child is larger than root

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

// If right child is larger than largest

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

// If largest is not root

if (largest != i)
{
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;

// Recursively call the swap_largest

swap_largest(arr, n, largest);
}
}
void heap(int arr[], int n)
{

// Build heap from an unsorted array (rearrange array)

for (int i = n / 2 - 1; i >= 0; i--)
swap_largest(arr, n, i);

// One by one extract an element from heap

for (int i = n - 1; i >= 0; i--)
{

// Move current root to end

temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

// call swap_largest on the reduced heap

swap_largest(arr, i, 0);
}
}
int print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int n, i;
scanf("%d", &n);
int arr[n];
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
heap(arr, n);
print(arr, n);
}
#include<iostream>
using namespace std;
int temp;
void swap_largest(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int left = 2*i + 1;
int right = 2*i + 2;

// If left child is larger than root

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

// If right child is larger than largest

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

// If largest is not root

if (largest != i)
{
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// Recursively call the swap_largest
swap_largest(arr, n, largest);
}
}
void heap(int arr[], int n)
{

// Build heap from an unsorted array (rearrange array)

for (int i = n / 2 - 1; i >= 0; i--)
swap_largest(arr, n, i);

// One by one extract an element from heap

for (int i = n - 1; i >= 0; i--)
{

// Move current root to end

temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

// call swap_largest on the reduced heap

swap_largest(arr, i, 0);
}
}
int print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}

int main()
{
int n, i;
cin >> n;
int arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
heap(arr, n);
print(arr, n);
}
import java.util.Scanner;
public class Main
{
public static void swap_largest(int arr[], int n, int i)
{
int temp;
int largest = i; // Initialize largest as root
int left = 2*i + 1;
int right = 2*i + 2;
// If left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;

// If right child is larger than largest

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

// If largest is not root

if (largest != i)
{
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;

// Recursively call the swap_largest
swap_largest(arr, n, largest);
}
}
public static void heap(int arr[], int n)
{
int temp;

// Build heap from an unsorted array (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
swap_largest(arr, n, i);

// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--)
{
// Move current root to end
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

// call swap_largest on the reduced heap
swap_largest(arr, i, 0);
}
}
public static void print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
}

public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int i;
int n = sc.nextInt();
int arr[] = new int[n];
for(i = 0; i < n; i++)
{
arr[i] = sc.nextInt();
}
heap(arr, n);
print(arr, n);
}
}

Heap Sort Time Complexity

To calculate the time complexity of heap sort, let us first try to break down & understand the time-complexities of individual functions.

  • To build max heap the actual complexity is O(n).
  • The complexity to swap the largest element with the last element of the array is O(log n).

Since Heapsort runs in linearithmic time, the combination of these two-time complexities is O(n logn) and hence the time complexity of Heap sort is O(n logn).