Heap Sort
Heap Sort Algorithm in C++ (Complete Implementation)
C++ Heap Sort Program
This program helps you to learn the fundamental structure and syntax of C++ programming.
#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) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Extract elements from heap one by one
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
heapSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}Original array: 64 34 25 12 22 11 90 Sorted array: 11 12 22 25 34 64 90
Understanding Heap Sort
This program teaches you how to implement the Heap Sort algorithm in C++. Heap Sort uses a binary heap data structure to sort elements efficiently. It first builds a max heap from the array, then repeatedly extracts the maximum element and places it at the end. Heap Sort guarantees O(n log n) performance in all cases and sorts in-place.
---
1. What This Program Does
The program sorts an array of integers using the Heap Sort algorithm. For example:
Heap Sort works by treating the array as a binary heap, building a max heap, and then repeatedly extracting the maximum element to build the sorted array from the end.
---
2. Header File Used
This header provides:
---
#include <iostream>3. Understanding Heap Sort
Binary Heap Concept
:
Algorithm Steps
:
Visual Example
:
Build Max Heap:
90
/ \
34 64
/ \ / \
12 22 25 11
Extract Max (90) → place at end
Heapify remaining...
---
4. Function: heapify()
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);
}
}
How it works
:
Heap Property
:
---
5. Function: heapSort()
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Extract elements from heap
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
// Build max heapHow it works
:
-
Build Heap
: Start from last non-leaf node (n/2 - 1), heapify upward
-
Extract
: Swap root (max) with last element, reduce heap size
-
Heapify
: Restore heap property after swap
---
6. Step-by-Step Algorithm
Step 1: Build Max Heap
Step 2: Extract Maximum
Step 3: Restore Heap
Step 4: Repeat
---
7. Understanding Binary Heap
Array Representation
:
Example
(array indices):
0 1 2 3 4 5 6
Tree:
0(90)
/ \
1(34) 2(64)
/ \ / \
3(12) 4(22) 5(25) 6(11)
Heap Property
:
---
8. Time and Space Complexity
Time Complexity
: O(n log n) in all cases
Space Complexity
: O(1)
Stability
: Not Stable
---
9. When to Use Heap Sort
Best For
:
Not Recommended For
:
---
10. Important Considerations
Building Heap
:
Heap Size
:
Heapify Direction
:
---
11. return 0;
This ends the program successfully.
---
Summary
This program is fundamental for beginners learning heap data structures, understanding guaranteed performance algorithms, and preparing for priority queues and advanced data structures in C++ programs.
Let us now understand every line and the components of the above program.
Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.
Practical Learning Notes for Heap Sort
This C++ program is part of the "Sorting & Searching Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.
A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.
For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.