Heap Sort in C++

July 14, 2025

What is heap sort in C++?

Heap Sort in C++ – A heap is a complete binary tree which is represented using array or sequential representation. It is one of the efficient algorithm for sorting given data in logical order.

In this sorting algorithm a tree structure called heap is used where a heap is a type of binary tree. An ordered balanced binary tree is called a Min-heap, where the value at the root of any subtree is less than or equal to the value of either of its children. An ordered balanced binary tree is called a max heap where the value at the root of any subtree is more than or equal to the value of either of its children. In this article, we will learn more about heap sort in C++

What is heap sort in C++?

A heap is a complete binary tree which is represented using array or sequential representation. It is one of the efficient algorithm for sorting given data in logical order.

Working of heap sort in C++

To sort any list into a logical order following steps are followed :-

Convert the list into heap.
Now convert this heap into max heap.
As the heap is converted to max heap largest element in the list is stored in the root of the heap, replace it with the last item of the heap.
Now delete this node and reduce the size of heap by 1.
Follow these steps until the list is sorted.

How to convert given list into heap ?

Let say, the index of any element in the list is i, the element in the index 2i+1 will become the left child and element in 2i+2 index will become the right child. And we want to find out the parent of any element then we can find it by finding the lower bound which is given by (i-1)/2 .

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Algorithm for heap sort in C++

MAX-HEAPIFY(A,i)
1- i<-left[i]
2- r<-right[i]
3- if l<heap-size[A]and A[l]>A[i]
4- then largest<-1
5- else largest<-i
6- if r<heap-size[A] and A[r]>A[largest]
7- then largest<-r
8- if largest!=i
9- then exchange A[i]<->A[largest]
10- MAX-HEAPIFY[A,largest]

HEAP-SORT(A)
1- BUILD-MAX-HEAP(A)
2- for i<-length[A] down to 2
3- do exchange A[1]<-> heap-size[A]-1
4- heap-size[A]<-heap-size[A]-1
5- MAX-HEAPIFY(A,1)

BUILD-MAX-HEAP(A)
1- heap-size[A]<-length[A]
2- for i<-(length[A]/2) down to 1 do
3- MAX-HEAPIFY(A,i)

Program for heap sort in C++

Run

#include<iostream>

using namespace std;

void heapify(int arr[], int n, int i)
{
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;
 
    //If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;
 
    //If right child largest 
    if (r < n && arr[r] > arr[largest])
        largest = r;
 
    //If root is nor largest
    if (largest != i)
    {
        swap(arr[i], arr[largest]);
 
        //Recursively heapifying the sub-tree
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n)
{
    
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
 
    //One by one extract an element from heap
    for (int i=n-1; i>=0; i--)
    {
        //Moving current root to end
        swap(arr[0], arr[i]);
 
        //Calling max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}
 
//Function to print array
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << "\n";
}
 

int main()
{
    int arr[] = {1, 14, 3, 7, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Unsorted array  \n";
    display(arr, n);
    
    heapSort(arr, n);
 
    cout << "Sorted array  \n";
    display(arr, n);
}

Output:
Unsorted array  
1	14	3	7	0	
Sorted array  
0	1	3	7	14

Time and Space Complexity for Heap Sort in C++

Time Complexity of Heap Sort

Heap Sort works by first building a max heap from the input, then repeatedly removing the largest element and placing it at the end of the array.

Let n be the number of elements.

Best Case: O(n log n)
Even if the array is already sorted, Heap Sort still builds a heap and sorts all elements.
Average Case: O(n log n)
On average, it takes log n time to adjust the heap for each of the n elements.
Worst Case: O(n log n)
Even in the worst case, Heap Sort performs log n operations for each element.

Space Complexity of Heap Sort

Heap Sort is an in-place algorithm, which means it does not use extra space for sorting (other than a few variables).

Space Complexity: O(1)
It sorts the array using constant extra space.

Quiz Time

Question 1.Which of the following sorting algorithms in its typical implementation gives best performance when applied on a sorted array?

Quick Sort
Heap Sort
Insertion Sort
Merge

Solution & Explanation

Insertion sort takes linear time when input array is sorted or almost sorted. All other sorting algorithms mentioned above will take more than linear time in their typical implementation.

Ans. Insertion Sort (C)

Question 2. What is the time complexity of Build Heap operation. Which is used to create a max(or min) binary heap from a given array.?

O(n)
O(log n)
O(nlog n)
None of the above

Solution & Explanation

BUILD-HEAP(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 
END

Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n).

Ans: A

Quiz Time

Question 1.Which of the following sorting algorithms in its typical implementation gives best performance when applied on a sorted array?

Quick Sort
Heap Sort
Insertion Sort
Merge

Solution & Explanation

Insertion sort takes linear time when input array is sorted or almost sorted. All other sorting algorithms mentioned above will take more than linear time in their typical implementation.

Ans. Insertion Sort (C)

Question 2. What is the time complexity of Build Heap operation. Which is used to create a max(or min) binary heap from a given array.?

O(n)
O(log n)
O(nlog n)
None of the above

Solution & Explanation

BUILD-HEAP(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 
END

Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n).

Ans: A

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Heap Sort Program in C

March 18, 2025

Heap Sort in C

A heap is a complete binary tree which is represented using array or sequential representation.

It is a special balanced binary tree data structure where root node is compared with its children and arranged accordingly.Normally in max heap parent node is always has a value greater then child node.

The worst and Average complexity of heap sort is O(n log₂ n).

From the given array, build the initial max heap.
Interchange the root element with the last element.
Use repetitive downward operation from root node to rebuild the heap of size one less than the starting.

Algorithm of Heap Sort

HEAP-SORT(A)
1- BUILD-MAX-HEAP(A)
2- for i<-length[A] down to 2
3- do exchange A[1]<-> heap-size[A]-1
4- heap-size[A]<-heap-size[A]-1
5- MAX-HEAPIFY(A,1)

BUILD-MAX-HEAP(A)
1- heap-size[A]<-length[A]
2- for i<-(length[A]/2) down to 1 do
3- MAX-HEAPIFY(A,i)

Implementation of Heap Sort

As we know that heap sort is based on the tree structure.

so we will take an example of heap sort with the based on tree.

Originally the given array is :[6,14,3,25,2,10,20,7,6]

First we call Build-max heap

heap size[A]=9

so,i=4 to 1, call MAX HEAPIFY (A,i)

i.e., first we call MAX HEAPIFY (A,4)

A[l]=7, A[i]=A[4] = 25,A[r] = 6

l<- left[4] = 8

r<-right[4] = 9

8<9 and 7>25 (false)

Then,largest <-4

9<9 and 6>25(false)

Then,largest = 4

A[i]<-> A[4]

Now call MAX HEAPIFY (A,2)

the A[length] =9

So, i=A/2 = 9/2 =4

i=4

since the parent node is greater than its child node.

If it is parent node is greater than child node then the parent node replace with the lesser child node.

similarly for i=3,2,1 we get the following heap tree.

Now call MAX HEAPIFY

Now we will replace the root node to last child In this photo is shown by replace 25 to 6.

Now call MAX HEAPIFY

Now we will replace the root node to last child In this photo is shown by replace 20 to 6.

Again call MAX HEAPIFY,

we get exchange A[14] and A[3] which is shown by a image.

Again call MAX HEAPIFY,

we get exchange A[10] and A[3] which is shown by a image.

Similarly,call MAX HEAPIFY

we’ll interchange A[7] and A[2]. which is shown by this image.

Similarly,call MAX HEAPIFY

we’ll interchange A[6] and A[3]. which is shown by this image.

Similarly,call MAX HEAPIFY

we’ll interchange A[6] and A[2]. which is shown by this image.

Final,call MAX HEAPIFY

we’ll interchange A[3] and A[2]. which is shown by this image.

and finally array will be sorted.

C Code of Heap Sort

Run

#include<stdio.h> // including library files 
int temp;
void heapify(int arr[], int size, int i)//declaring functions
{
int max = i;
int left = 2*i + 1;
int right = 2*i + 2;

if (left < size && arr[left] >arr[max])
max= left;

if (right < size && arr[right] > arr[max])
max= right;

if (max!= i)
{
// performing sorting logic by using temporary variable
temp = arr[i];
arr[i]= arr[max];
arr[max] = temp;
heapify(arr, size, max);
}
}

void heapSort(int arr[], int size)// providing definition to heap sort
{
int i;
for (i = size / 2 - 1; i >= 0; i--)
heapify(arr, size, i);
for (i=size-1; i>=0; i--)
{
// swaping logic
temp = arr[0];
arr[0]= arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}

void main() // defining main()
{
int arr[] = {58, 134, 3, 67, 32, 89, 15, 10,78, 9};
// array initializing with their elements.
int i;
int size = sizeof(arr)/sizeof(arr[0]);

heapSort(arr, size);

printf("printing sorted elements\n"); // printing the sorted array
for (i=0; i<size; ++i)
printf("%d ",arr[i]);
}

Output

printing sorted elements
3 9 10 15 32 58 67 78 89 134

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Classification of Sorting Algorithms
Bubble Sort – C | C++ | Java
Insertion Sort – C | C++ | Java
Selection Sort – C | C++ | Java
Merge Sort – C | C++ | Java
Quick Sort – C | C++ | Java
Counting Sort – C | C++ | Java
Radix Sort – C | C++ | Java
Heap Sort – C | C++

Unlock this article for Free, by logging in

Heap Sort in C++

What is heap sort in C++?

What is heap sort in C++?

Working of heap sort in C++

How to convert given list into heap ?

Prime Course Trailer

Related Banners

Algorithm for heap sort in C++

Program for heap sort in C++

Time and Space Complexity for Heap Sort in C++

Time Complexity of Heap Sort

Space Complexity of Heap Sort

Quiz Time

Quiz Time

Get over 200+ course One Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Heap Sort Program in C

Heap Sort in C

Algorithm of Heap Sort

Implementation of Heap Sort

C Code of Heap Sort

Output

Sorting

Unlock this article for Free,
by logging in