Heap Sort Algorithm in DSA C++ - Build from Scratch

Heap Sort Algorithm

📖 Scenario: You are working on a program that needs to sort a list of numbers efficiently. Heap sort is a great way to do this by using a special tree structure called a heap.Imagine you have a messy pile of books and you want to arrange them from smallest to largest by height. Heap sort helps you organize them step by step.

🎯 Goal: Build a C++ program that sorts an array of integers using the heap sort algorithm. You will create the array, set up helper variables, write the heapify function, and then perform the sorting. Finally, you will print the sorted array.

📋 What You'll Learn

Create an integer array with exact values: 12, 11, 13, 5, 6, 7

Create an integer variable n to store the size of the array

Write a heapify function that maintains the max heap property

Implement the heap sort logic using the heapify function

Print the sorted array in ascending order separated by spaces

💡 Why This Matters

🌍 Real World

Heap sort is used in systems where guaranteed O(n log n) sorting time is needed, such as in embedded systems or real-time applications.

💼 Career

Understanding heap sort helps in technical interviews and improves problem-solving skills related to priority queues and efficient sorting.

1

Create the array and its size

Create an integer array called arr with these exact values: 12, 11, 13, 5, 6, 7. Then create an integer variable called n and set it to the size of arr.

DSA C++

# Create the array 'arr' and integer 'n' for its size
// Your code here

Hint

Use int arr[] = {12, 11, 13, 5, 6, 7}; to create the array. Use sizeof(arr) / sizeof(arr[0]) to find the size.

2

Write the heapify function

Write a function called heapify that takes three parameters: an integer array arr, an integer n for the size of the heap, and an integer i for the index to heapify. This function should maintain the max heap property by comparing the parent node with its children and swapping if needed.

DSA C++

#include 
using namespace std;

void heapify(int arr[], int n, int i) {
    // Your code here
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    return 0;
}

Hint

Remember to check left and right children indices and swap with the largest if needed. Use recursion to heapify the affected subtree.

3

Implement the heap sort logic

In the main function, first build a max heap by calling heapify on all non-leaf nodes from n/2 - 1 down to 0. Then, extract elements one by one from the heap by swapping the root with the last element and calling heapify on the reduced heap.

DSA C++

#include 
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  arr[largest])
        largest = left;

    if (right  arr[largest])
        largest = right;

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

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Build max heap
    // Your code here

    // Extract elements from heap
    // Your code here

    return 0;
}

Hint

First build the max heap by heapifying from the middle to the start. Then swap the root with the last element and heapify the reduced heap repeatedly.

4

Print the sorted array

After sorting, print the elements of arr separated by spaces in one line using a for loop.

DSA C++

#include 
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  arr[largest])
        largest = left;

    if (right  arr[largest])
        largest = right;

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

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    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);
    }

    // Print the sorted array
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Hint

Use a for loop from 0 to n-1 and print each element followed by a space. End with cout << endl;.

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