Sorting plays a very important role in programming. It helps in arranging data in a specific order, making it easier to search, analyze, or display. One of the most powerful and efficient sorting algorithms in computer science is the Heap Sort algorithm. It is known for its excellent performance and ability to sort large amounts of data quickly without requiring much extra memory.
with hands-on learning.
get the skills and confidence to land your next move.
Heap Sort is based on the concept of a binary heap data structure, which is a special kind of complete binary tree. In this tree, the parent node is always greater (in a max heap) or smaller (in a min heap) than its child nodes. The algorithm works in two main steps — first, it builds a heap from the data, and then it repeatedly extracts the largest (or smallest) element from the heap and places it in the sorted part of the array. The result is a neatly sorted list of elements.
One of the best things about Heap Sort is that it always performs in O(n log n) time, even in the worst case. It’s not a stable sort like Merge Sort, but it’s in-place, meaning it doesn’t need extra space for sorting. Because of this, Heap Sort is widely used in embedded systems, scheduling problems, and large datasets where efficiency and memory usage are both important. Let’s explore how to implement Heap Sort in C++ using different methods.
Program 1: Basic Heap Sort using Loops
This first example demonstrates the standard way to implement Heap Sort using a max heap. It uses predefined data and sorts the elements in ascending order.
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
int arr[] {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array in ascending order: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}In this program, the heapify() function ensures that the heap property is maintained — meaning the parent node is always greater than its children. The heapSort() function first builds the heap and then repeatedly extracts the largest element by swapping it with the last element of the heap. This continues until all elements are sorted. Beginners can easily understand this code because it uses clear loops and a simple recursive call to maintain the heap structure.
Program 2: Heap Sort using Recursion for Building Heap
This version of the Heap Sort algorithm focuses more on using recursion in both heap construction and sorting. It helps learners understand how recursion simplifies logic by breaking the task into smaller steps.
#include <iostream>
using namespace std;
void heapifyRecursive(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapifyRecursive(arr, n, largest);
}
}
void buildHeapRecursive(int arr[], int n, int i) {
if (i < 0)
return;
heapifyRecursive(arr, n, i);
buildHeapRecursive(arr, n, i - 1);
}
void heapSortRecursive(int arr[], int n) {
buildHeapRecursive(arr, n, n / 2 - 1);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapifyRecursive(arr, i, 0);
}
}
int main() {
int arr[] {40, 10, 30, 50, 20};
int n = sizeof(arr) / sizeof(arr[0]);
heapSortRecursive(arr, n);
cout << "Sorted array using recursion: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}Here, both heap creation and maintenance use recursion. The function buildHeapRecursive() recursively calls itself to build the heap from bottom to top, and the heapifyRecursive() function ensures the heap property is satisfied after each swap. This makes the logic easier to follow, especially for those already familiar with recursive algorithms like Merge Sort or Quick Sort.
Program 3: Heap Sort for Descending Order
Sometimes, we need data sorted from largest to smallest — for example, when ranking results or prioritizing high scores. This version of Heap Sort creates a min heap instead of a max heap, resulting in descending order sorting.
#include <iostream>
using namespace std;
void minHeapify(int arr[], int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest])
smallest = left;
if (right < n && arr[right] < arr[smallest])
smallest = right;
if (smallest != i) {
swap(arr[i], arr[smallest]);
minHeapify(arr, n, smallest);
}
}
void heapSortDescending(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
minHeapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
minHeapify(arr, i, 0);
}
}
int main() {
int arr[] {15, 3, 27, 12, 8, 20};
int n = sizeof(arr) / sizeof(arr[0]);
heapSortDescending(arr, n);
cout << "Sorted array in descending order: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}The only change here is that the heap property now ensures the smallest element is always at the top instead of the largest. This simple adjustment flips the order of sorting, demonstrating how flexible Heap Sort is. Beginners can easily understand that by changing one comparison, the algorithm can produce completely different results.
Program 4: Heap Sort for Strings
Heap Sort isn’t limited to numbers — it can also sort text or words alphabetically. This version uses an array of strings and sorts them in ascending order.
#include <iostream>
#include <string>
using namespace std;
void heapify(string arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(string arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
string arr[] {"Banana", "Apple", "Peach", "Mango", "Cherry"};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Words sorted alphabetically: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}The same heap-building concept applies to strings. C++ allows string comparisons using the greater-than (>) and less-than (<) operators, making it easy to adapt numerical sorting algorithms for text data. This example helps learners see how Heap Sort can be applied to a wide range of data types beyond just numbers.
Frequently Asked Questions (FAQ)
Here are some common questions beginners often ask about Heap Sort in C++.
Q1: What is Heap Sort in C++?
Heap Sort is a comparison-based sorting algorithm that builds a binary heap and repeatedly extracts the top element (largest or smallest) to produce a sorted array.
Q2: Why is Heap Sort efficient?
It has a consistent time complexity of O(n log n) and does not require extra memory like Merge Sort, making it both fast and space-efficient.
Q3: Is Heap Sort stable?
No, Heap Sort is not a stable sorting algorithm because equal elements might not maintain their original order.
Q4: Can Heap Sort work on strings?
Yes, it can sort strings alphabetically by using the same logic, as string comparisons in C++ are supported naturally.
Q5: What is the difference between Max Heap and Min Heap?
A Max Heap keeps the largest element at the top, while a Min Heap keeps the smallest. Max Heaps are used for ascending order sorting, and Min Heaps for descending order.
Conclusion
Heap Sort is one of the most reliable and efficient sorting algorithms in C++. It showcases the power of the heap data structure and how it can be used to organize data quickly and effectively. With its consistent performance and minimal memory usage, Heap Sort is a favorite in performance-critical applications.
In this article, we explored several versions of the C++ Heap Sort program, including the basic iterative version, a recursive implementation, descending order sorting, and sorting strings alphabetically. Each version shows how versatile and adaptable the algorithm can be.
If you are learning C++, take time to practice these examples. Try using different arrays, modify the heap type, and watch how the output changes. The more you experiment, the more you’ll understand how Heap Sort works at its core. With practice, sorting algorithms like Heap Sort will feel as natural as writing simple loops.
