C++ Program for Heap Sort with Example and Explanation

A C++ program for heap sort uses a heapify function to build a max heap and then repeatedly swaps the root with the last element, reducing the heap size and calling heapify again; the main code includes building the heap and sorting the array in-place.

Examples

Inputarr = {4, 10, 3, 5, 1}

OutputSorted array: 1 3 4 5 10

Inputarr = {12, 11, 13, 5, 6, 7}

OutputSorted array: 5 6 7 11 12 13

Inputarr = {1}

OutputSorted array: 1

How to Think About It

Heap sort works by first turning the array into a max heap, where the largest value is at the root. Then, it swaps the root with the last element and reduces the heap size, repeating the process to sort the array in ascending order.

Algorithm

1

Build a max heap from the input array.

2

Swap the root (maximum) with the last element of the heap.

3

Reduce the heap size by one.

4

Call heapify on the root to maintain the max heap property.

5

Repeat steps 2-4 until the heap size is 1.

Code

cpp

#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[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

Output

Sorted array: 1 3 4 5 10 

Dry Run

Let's trace the array {4, 10, 3, 5, 1} through the heap sort code.

1

Build max heap

Start heapify from index 1: array becomes {4, 10, 3, 5, 1}, then from index 0: array becomes {10, 5, 3, 4, 1}

2

Swap root with last element

Swap arr[0]=10 with arr[4]=1, array becomes {1, 5, 3, 4, 10}

3

Heapify root for reduced heap

Heapify index 0 with size 4: array becomes {5, 4, 3, 1, 10}

4

Repeat swap and heapify

Swap arr[0]=5 with arr[3]=1, array becomes {1, 4, 3, 5, 10}, heapify index 0 size 3: array becomes {4, 1, 3, 5, 10}

5

Continue until sorted

Swap arr[0]=4 with arr[2]=3, array becomes {3, 1, 4, 5, 10}, heapify index 0 size 2: array becomes {3, 1, 4, 5, 10}, swap arr[0]=3 with arr[1]=1, array becomes {1, 3, 4, 5, 10}

Step	Array State
Build max heap	10 5 3 4 1
Swap root with last	1 5 3 4 10
Heapify root	5 4 3 1 10
Swap root with last	1 4 3 5 10
Heapify root	4 1 3 5 10
Swap root with last	3 1 4 5 10
Heapify root	3 1 4 5 10
Swap root with last	1 3 4 5 10

Why This Works

Step 1: Building the max heap

The heapify function ensures the subtree rooted at an index satisfies the max heap property, so the largest element moves to the root.

Step 2: Extracting the max element

Swapping the root with the last element places the largest value at its correct sorted position.

Step 3: Maintaining the heap

After swapping, calling heapify on the root restores the max heap property for the reduced heap.

Alternative Approaches

Using STL priority_queue

cpp

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {4, 10, 3, 5, 1};
    priority_queue<int> pq(arr.begin(), arr.end());
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    return 0;
}

This uses a max heap internally but outputs in descending order; requires extra space and does not sort in-place.

Recursive heap sort with separate buildHeap

cpp

#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 buildHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
}

void heapSort(int arr[], int n) {
    buildHeap(arr, n);
    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);
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}

Separates heap building for clarity but same complexity and in-place sorting.

Complexity: O(n log n) time, O(1) space

Time Complexity

Building the heap takes O(n) time, and each of the n-1 removals takes O(log n) to heapify, resulting in O(n log n) overall.

Space Complexity

Heap sort sorts the array in-place using only a few variables, so it uses O(1) extra space.

Which Approach is Fastest?

Heap sort is efficient and in-place, but quicksort is often faster in practice; using STL priority_queue is simpler but uses extra space.

Approach	Time	Space	Best For
Heap Sort	O(n log n)	O(1)	In-place sorting with guaranteed time
STL priority_queue	O(n log n)	O(n)	Simple max heap usage, not in-place
Quicksort (not shown)	O(n log n) average	O(log n)	Faster average case, but not stable