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.

Practice

1. What is the main purpose of the heapify operation in the Heap Sort Algorithm?

easy

A. To reverse the array elements

B. To sort the array directly without building a heap

C. To swap the first and last elements of the array

D. To build a max heap or min heap from an unordered array

Solution

1. Step 1: Understand heapify's role

   Heapify rearranges elements to satisfy the heap property, making the array a max heap or min heap.

2. Step 2: Connect heapify to heap sort

   Heap sort uses heapify to build the heap before sorting by repeatedly extracting the root.

3. Final Answer:

   To build a max heap or min heap from an unordered array -> Option D

4. Quick Check:

   Heapify builds heap = A [OK]

Hint: Heapify creates heap structure before sorting [OK]

Common Mistakes:

• Thinking heapify sorts the array directly
• Confusing heapify with swapping elements
• Assuming heapify reverses the array

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[j] in C++ during heap sort?

easy

A. arr.swap(i, j);

B. arr[i] = arr[j]; arr[j] = arr[i];

C. swap(arr[i], arr[j]);

D. swap arr[i], arr[j];

Solution

1. Step 1: Recall C++ swap syntax

   The standard way to swap two elements is using the swap() function with parentheses and commas.

2. Step 2: Check each option

   swap(arr[i], arr[j]); uses correct syntax. arr[i] = arr[j]; arr[j] = arr[i]; overwrites values incorrectly. swap arr[i], arr[j]; misses parentheses. arr.swap(i, j); is invalid method call.

3. Final Answer:

   swap(arr[i], arr[j]); -> Option C

4. Quick Check:

   Correct swap syntax = D [OK]

Hint: Use swap() with parentheses and commas in C++ [OK]

Common Mistakes:

• Assigning values instead of swapping
• Missing parentheses in swap function
• Using non-existent swap methods

3. What will be the output array after applying heap sort on arr = [4, 10, 3, 5, 1]? Print the sorted array.

medium

A. [1, 3, 4, 5, 10]

B. [10, 5, 4, 3, 1]

C. [1, 4, 3, 5, 10]

D. [5, 10, 4, 3, 1]

Solution

1. Step 1: Build max heap from array

   Max heap of [4,10,3,5,1] rearranges to [10,5,3,4,1].

2. Step 2: Extract max and heapify repeatedly

   Extract 10, heapify remaining; then 5, then 4, then 3, then 1 results in sorted ascending array [1,3,4,5,10].

3. Final Answer:

   [1, 3, 4, 5, 10] -> Option A

4. Quick Check:

   Heap sort ascending = [1,3,4,5,10] [OK]

Hint: Heap sort outputs ascending sorted array [OK]

Common Mistakes:

• Confusing max heap with sorted array
• Reading heap array as sorted directly
• Outputting descending order instead

4. Identify the error in this heap sort snippet and choose the correct fix:

void heapify(int arr[], int n, int i) {
  int largest = i;
  int left = 2*i;
  int right = 2*i + 1;
  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);
  }
}

medium

A. Remove recursive call to heapify

B. Change left and right to 2*i + 1 and 2*i + 2 respectively

C. Change largest initialization to 0

D. Change swap to arr[i] = arr[largest]

Solution

1. Step 1: Check child index calculation

   In 0-based arrays, left child = 2*i + 1, right child = 2*i + 2. Current code uses 2*i and 2*i + 1 which is incorrect.

2. Step 2: Fix child indices

   Changing left and right to 2*i + 1 and 2*i + 2 fixes indexing and prevents out-of-bound errors.

3. Final Answer:

   Change left and right to 2*i + 1 and 2*i + 2 respectively -> Option B

4. Quick Check:

   Child indices = 2*i+1, 2*i+2 [OK]

Hint: Use 0-based indexing: left=2*i+1, right=2*i+2 [OK]

Common Mistakes:

• Using 1-based indexing formulas in 0-based arrays
• Removing recursion breaks heapify
• Incorrect swap assignment instead of swap function

5. Given an array arr = [12, 11, 13, 5, 6, 7], how many times will the heapify function be called during the build heap phase of heap sort?

hard

A. 4 times

B. 3 times

C. 2 times

D. 5 times

Solution

1. Step 1: Understand build heap calls

   Build heap calls heapify from last non-leaf node down to root. For array size 6, last non-leaf node is at index 2 (0-based).

2. Step 2: Count heapify calls

   Heapify called at indices 2, 1, 0 during build heap phase, totaling 3 calls. However, heapify may call itself recursively inside these calls. Counting only initial calls, it's 3.

3. Step 3: Clarify question intent

   If question means initial calls only, answer is 3. If counting recursive calls inside heapify, index 1 and 0 calls may cause extra heapify calls. For this array, heapify at index 1 calls heapify at index 4 (leaf, no call), index 0 calls heapify at index 1 again, so total calls are 4.

4. Final Answer:

   4 times -> Option A

5. Quick Check:

   Build heap calls heapify 3 + 1 recursive = 4 [OK]

Hint: Count initial + recursive heapify calls during build heap [OK]

Common Mistakes:

• Counting only initial calls, ignoring recursion
• Confusing build heap with sorting phase calls
• Misidentifying last non-leaf node index