Heap Sort Algorithm in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Heap Sort on a small array

What is the output of the following C++ code after performing heap sort on the array?

DSA C++

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) {
        std::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--) {
        std::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);
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

A 3 1 4 5 10

B 10 5 4 3 1

C 1 4 3 5 10

D 1 3 4 5 10

💡 Hint

Heap sort sorts the array in ascending order by building a max heap first.

Heap sort first builds a max heap, then repeatedly swaps the root with the last element and heapifies the reduced heap. The final output is the array sorted in ascending order.

🧠 Conceptual

intermediate

Understanding heapify function behavior

What is the main purpose of the heapify function in the heap sort algorithm?

A To sort the array directly without building a heap

B To swap the first and last elements of the array

C To build a max heap from an unordered array segment

D To reverse the array elements

💡 Hint

Heapify ensures the heap property for a subtree rooted at a given index.

Heapify rearranges elements to maintain the max heap property for the subtree rooted at the given index, ensuring the parent node is larger than its children.

❓ Predict Output

advanced

Output after partial heap sort steps

Given the array {7, 2, 6, 3, 9} and the heap sort algorithm, what is the array state after the first swap and heapify in the sorting phase?

DSA C++

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) {
        std::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);

    std::swap(arr[0], arr[n-1]);
    heapify(arr, n-1, 0);
}

int main() {
    int arr[] = {7, 2, 6, 3, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

A 6 3 2 7 9

B 7 3 6 2 9

C 3 2 6 7 9

D 2 3 6 7 9

💡 Hint

After building the max heap, the largest element is swapped with the last element, then heapify is called on the reduced heap.

Initial max heap is built: {9, 7, 6, 3, 2}. Swap root (9) with last element (2) gives {2, 7, 6, 3, 9}. Heapify on first 4 elements rearranges to {7, 3, 6, 2, 9}.

🔧 Debug

advanced

Identify the error in heapify implementation

What error will the following heapify function cause when called during heap sort?

DSA C++

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) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

A Array index out of bounds error

B No error, works correctly

C Infinite recursion causing stack overflow

D Compilation error due to wrong syntax

💡 Hint

Check how left and right child indices are calculated for a zero-based array.

The left and right child indices are incorrectly calculated for zero-based indexing. They should be 2*i + 1 and 2*i + 2. Using 2*i and 2*i + 1 can cause accessing invalid indices leading to out of bounds errors.

🚀 Application

expert

Heap sort stability and behavior

Which statement about heap sort is true?

A Heap sort is unstable and may change the relative order of equal elements

B Heap sort requires extra memory proportional to the array size

C Heap sort always sorts in descending order by default

D Heap sort is stable and maintains the relative order of equal elements

💡 Hint

Consider how heap sort swaps elements during sorting.

Heap sort is not stable because it swaps elements that may be equal, changing their original order. It sorts in ascending order by default and works in-place without extra memory proportional to input size.

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