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 heap sort code on the array [4, 10, 3, 5, 1]?

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) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        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--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {4, 10, 3, 5, 1};
    int n = 5;
    heapSort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

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

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

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

D [1, 4, 3, 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 array is sorted ascending.

🧠 Conceptual

intermediate

Heap property in heap sort

Which property must the array satisfy after the first for-loop in the heapSort function?

A The array is sorted in ascending order.

B The array satisfies the max heap property.

C The array satisfies the min heap property.

D The array is reversed.

💡 Hint

The first loop builds a heap structure from the array.

The first loop builds a max heap from the array, so the array satisfies the max heap property before sorting starts.

🔧 Debug

advanced

Identify the bug in heapify function

What error will occur if the heapify function is called with i = -1?

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) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

A Compilation error due to invalid syntax.

B No error, function works correctly.

C Infinite recursion causing stack overflow.

D Array index out of bounds error due to negative index.

💡 Hint

Negative index access in C arrays is invalid.

If i is -1, left and right become negative or invalid indices, causing out of bounds access.

❓ Predict Output

advanced

Heap sort output with duplicate elements

What is the output of heap sort on the array [2, 3, 3, 1, 2]?

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) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        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--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {2, 3, 3, 1, 2};
    int n = 5;
    heapSort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A [1, 2, 2, 3, 3]

B [3, 3, 2, 2, 1]

C [1, 3, 2, 2, 3]

D [2, 1, 2, 3, 3]

💡 Hint

Heap sort sorts duplicates in ascending order as well.

Heap sort sorts the array including duplicates in ascending order.

🧠 Conceptual

expert

Time complexity of heap sort

What is the worst-case time complexity of heap sort for an array of size n?

A O(n log n)

B O(n^2)

C O(log n)

D O(n)

💡 Hint

Heap sort builds a heap and then extracts elements one by one.

Building the heap takes O(n), and each of the n extractions takes O(log n), so total is O(n log n).

Practice

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

easy

A. To build a max heap or min heap from an unsorted array

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

C. To reverse the array elements

D. To count the number of elements in the array

Solution

1. Step 1: Understand heapify's role

   Heapify rearranges elements to satisfy heap property (max or min heap).

2. Step 2: Connect heapify to heap sort

   Heap sort uses heapify to build the heap before sorting.

3. Final Answer:

   To build a max heap or min heap from an unsorted array -> Option A

4. Quick Check:

   Heapify builds heap = To build a max heap or min heap from an unsorted array [OK]

Hint: Heapify creates heap structure from array [OK]

Common Mistakes:

• Confusing heapify with swapping elements
• Thinking heapify reverses the array
• Assuming heapify counts elements

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

easy

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

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

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

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

Solution

1. Step 1: Recall C swap syntax

   In C, swapping requires a temporary variable to hold one value.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses temp variable correctly; others are invalid in C.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option B

4. Quick Check:

   Use temp variable to swap in C = temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; [OK]

Hint: Use temp variable to swap in C [OK]

Common Mistakes:

• Trying Python-style swap syntax in C
• Assigning without temp causing overwrite
• Using undefined swap function

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

medium

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

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

C. [1, 3, 4, 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 sort

   Repeatedly swap max with last element and heapify to get sorted array [1,3,4,5,10].

3. Final Answer:

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

4. Quick Check:

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

Hint: Heap sort outputs sorted ascending array [OK]

Common Mistakes:

• Confusing max heap with sorted array
• Forgetting to heapify after swaps
• Assuming heap sort outputs descending order

4. Identify the error in this heap sort snippet in 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) {
    int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
    heapify(arr, n, largest);
  }
}

medium

A. The recursive call to heapify is missing

B. The swap logic is incorrect

C. The base case for recursion is missing

D. Left and right child indices should be 2*i + 1 and 2*i + 2

Solution

1. Step 1: Check child index calculation

   In 0-based arrays, left child = 2*i + 1, right child = 2*i + 2.

2. Step 2: Verify other parts

   Swap and recursion are correct; base case is implicit by condition checks.

3. Final Answer:

   Left and right child indices should be 2*i + 1 and 2*i + 2 -> Option D

4. Quick Check:

   Child indices in 0-based heap = 2*i+1, 2*i+2 [OK]

Hint: Remember 0-based heap child indices [OK]

Common Mistakes:

• Using 1-based indexing formulas in 0-based arrays
• Ignoring recursive heapify call
• Misplacing swap logic

5. Given an array with many duplicate elements, how does heap sort behave compared to quicksort in terms of stability and performance?

hard

A. Heap sort is not stable but has consistent O(n log n) time; quicksort is unstable and may degrade to O(n²)

B. Heap sort is stable and faster than quicksort always

C. Heap sort is stable but slower than quicksort in all cases

D. Heap sort and quicksort are both stable and have same worst-case time

Solution

1. Step 1: Understand stability of heap sort

   Heap sort is not stable because it swaps elements without preserving order of equal keys.

2. Step 2: Compare performance with quicksort

   Heap sort guarantees O(n log n) time always; quicksort is faster on average but can degrade to O(n²).

3. Final Answer:

   Heap sort is not stable but has consistent O(n log n) time; quicksort is unstable and may degrade to O(n²) -> Option A

4. Quick Check:

   Heap sort stable? No; Time? O(n log n) always [OK]

Hint: Heap sort stable? No; quicksort worst-case O(n²) [OK]

Common Mistakes:

• Assuming heap sort is stable
• Thinking quicksort worst-case is always O(n log n)
• Confusing stability with speed