Heap Sort in C++
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.
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++
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++
#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

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
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
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
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
Login/Signup to comment