Heap Sort Algorithm in DSA C++

Mental Model

Heap sort turns the list into a special tree called a heap where the biggest value is always on top, then removes the top repeatedly to sort the list.

Analogy: Imagine a pile of boxes stacked so the biggest box is always on top. You take the biggest box off, then rearrange the pile so the next biggest box is on top, repeating until all boxes are sorted.

Array: [4, 10, 3, 5, 1]
Heap tree:
       10
      /  \
     5    3
    / \
   4   1

Dry Run Walkthrough

Input: array: [4, 10, 3, 5, 1]

Goal: Sort the array in ascending order using heap sort

Step 1: Build max heap from array

[10, 5, 3, 4, 1]

Why: We rearrange the array so the largest value is at the root (index 0)

Step 2: Swap root (10) with last element (1), reduce heap size

[1, 5, 3, 4, 10]

Why: Move largest element to its correct final position at the end

Step 3: Heapify root to restore max heap

[5, 4, 3, 1, 10]

Why: Fix heap so largest element is again at root for next extraction

Step 4: Swap root (5) with last element in heap (1), reduce heap size

[1, 4, 3, 5, 10]

Why: Place next largest element in correct position

Step 5: Heapify root to restore max heap

[4, 1, 3, 5, 10]

Why: Restore heap property for remaining elements

Step 6: Swap root (4) with last element in heap (3), reduce heap size

[3, 1, 4, 5, 10]

Why: Place next largest element in correct position

Step 7: Heapify root to restore max heap

[3, 1, 4, 5, 10]

Why: Heap property is already satisfied, no change

Step 8: Swap root (3) with last element in heap (1), reduce heap size

[1, 3, 4, 5, 10]

Why: Place next largest element in correct position

Step 9: Heapify root to restore max heap

[3, 1, 4, 5, 10]

Why: Heap property is restored after heapify

Result:

Sorted array: [1, 3, 4, 5, 10]

Annotated Code

DSA C++

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

void heapify(vector<int>& arr, int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2 * i + 1; // left child index
    int right = 2 * i + 2; // right child index

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]); // swap root with largest child
        heapify(arr, n, largest); // recursively heapify the affected subtree
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();

    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i); // heapify from last non-leaf node up to root
    }

    // Extract elements from heap one by one
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]); // move current root to end
        heapify(arr, i, 0); // heapify reduced heap
    }
}

int main() {
    vector<int> arr = {4, 10, 3, 5, 1};
    heapSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

if (left < n && arr[left] > arr[largest])

Check if left child is larger than current largest

if (right < n && arr[right] > arr[largest])

Check if right child is larger than current largest

if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); }

Swap root with largest child and heapify subtree to maintain max heap

for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); }

Build max heap starting from last non-leaf node up to root

for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); }

Extract max element to end and heapify reduced heap

Output

1 3 4 5 10 

Complexity Analysis

Time: O(n log n) because building the heap takes O(n) and each of the n extractions takes O(log n) to heapify

Space: O(1) because heap sort sorts the array in place without extra storage

vs Alternative: Compared to simple sorts like bubble sort O(n^2), heap sort is much faster for large data due to efficient heap structure

Edge Cases

empty array

No operations happen, array remains empty

DSA C++

int n = arr.size(); (heapSort function handles zero size)

array with one element

Heapify and sort steps do nothing, array remains unchanged

DSA C++

for (int i = n / 2 - 1; i >= 0; i--) (loop skips if n=1)

array with all equal elements

Heapify swaps do not change order, array remains same

DSA C++

if (largest != i) condition prevents unnecessary swaps

When to Use This Pattern

When you need to sort data efficiently in place and can use a tree-like structure, heap sort is a good choice because it guarantees O(n log n) time without extra memory.

Common Mistakes

Mistake: Not building the max heap before sorting
Fix: Add the initial heap building loop from last non-leaf node up to root

Mistake: Heapifying the entire array after each swap instead of the reduced heap
Fix: Heapify only the reduced heap size after moving the max element to the end

Summary

Heap sort builds a max heap and repeatedly extracts the largest element to sort the array.

Use heap sort when you want an efficient in-place sorting algorithm with guaranteed O(n log n) time.

The key insight is maintaining the max heap property so the largest element is always at the root for easy extraction.