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#

using System;

class Program {
    static 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);
        }
    }

    static void HeapSort(int[] arr) {
        int n = arr.Length;

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

    static void Main() {
        int[] arr = {4, 10, 3, 5, 1};
        HeapSort(arr);
        Console.WriteLine(string.Join(" -> ", arr) + " -> null");
    }
}

A 1 -> 3 -> 4 -> 5 -> 10 -> null

B 10 -> 5 -> 4 -> 3 -> 1 -> null

C 5 -> 10 -> 4 -> 3 -> 1 -> null

D 1 -> 4 -> 3 -> 5 -> 10 -> null

💡 Hint

Heap sort sorts the array in ascending order by repeatedly moving the largest element to the end.

Heap sort builds a max heap, then swaps the root with the last element, reduces heap size, and heapifies again. The final array is sorted ascending.

🧠 Conceptual

intermediate

Heap Sort Time Complexity

What is the time complexity of heap sort in the average and worst cases?

A O(log n) average, O(n^2) worst case

B O(n^2) average, O(n log n) worst case

C O(n) average, O(n log n) worst case

D O(n log n) for both average and worst cases

💡 Hint

Heap sort always builds a heap and performs heapify operations.

Heap sort always takes O(n log n) time because building the heap is O(n) and each of the n removals takes O(log n).

🔧 Debug

advanced

Identify the error in heapify function

What error will occur when running this heapify function on an 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) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        Heapify(arr, n, largest);
    }
}

A StackOverflowException due to infinite recursion

B IndexOutOfRangeException due to invalid index access

C No error, function works correctly

D Compilation error due to missing return type

💡 Hint

Check the boundary conditions for left and right child indices.

The conditions use 'left <= n' and 'right <= n' which allow index n, but valid indices are 0 to n-1. This causes out of range access.

❓ Predict Output

advanced

Heap Sort on a reversed array

What is the output after heap sorting this reversed array?

DSA C#

using System;

class Program {
    static 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);
        }
    }

    static void HeapSort(int[] arr) {
        int n = arr.Length;

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

    static void Main() {
        int[] arr = {9, 7, 5, 3, 1};
        HeapSort(arr);
        Console.WriteLine(string.Join(" -> ", arr) + " -> null");
    }
}

A 1 -> 3 -> 5 -> 7 -> 9 -> null

B 9 -> 7 -> 5 -> 3 -> 1 -> null

C 3 -> 1 -> 5 -> 7 -> 9 -> null

D 1 -> 5 -> 3 -> 7 -> 9 -> null

💡 Hint

Heap sort always sorts ascending regardless of initial order.

Heap sort rearranges the reversed array into ascending order: 1, 3, 5, 7, 9.

🧠 Conceptual

expert

Heap Sort Stability

Is heap sort a stable sorting algorithm? Why or why not?

A Yes, because heap sort only swaps elements when necessary preserving order

B No, because heap sort uses extra memory that disrupts stability

C No, because heap sort swaps elements that can change the relative order of equal elements

D Yes, because heap sort builds a heap which maintains order

💡 Hint

Think about what happens when two equal elements are swapped during heapify.

Heap sort is not stable because it swaps elements during heapify that can reorder equal elements.

Practice

1. What is the main purpose of the heapify function in the Heap Sort algorithm?

easy

A. To build a max heap from an unordered array

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

C. To reverse the array after sorting

D. To count the number of elements in the array

Solution

1. Step 1: Understand heapify's role

   The heapify function rearranges elements to satisfy the max heap property, where each parent node is greater than its children.

2. Step 2: Connect heapify to building max heap

   Heapify is called repeatedly to build a max heap from an unordered array before sorting begins.

3. Final Answer:

   To build a max heap from an unordered array -> Option A

4. Quick Check:

   heapify builds max heap = A [OK]

Hint: Heapify creates max heap structure before sorting [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. swap(arr[i], arr[j]);

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

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

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

Solution

1. Step 1: Identify correct C# swap syntax

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

2. Step 2: Check each option

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temporary variable correctly. arr[i], arr[j] = arr[j], arr[i]; is Python syntax. swap(arr[i], arr[j]); is invalid without a swap method. arr[i] = arr[j]; arr[j] = arr[i]; overwrites values incorrectly.

3. Final Answer:

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

4. Quick Check:

   Use temp variable to swap in C# = C [OK]

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

Common Mistakes:

• Using Python tuple swap syntax in C#
• Calling undefined swap function
• Overwriting values without temp variable

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

medium

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

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

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

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

Solution

1. Step 1: Build max heap from array

   Starting array: [4, 10, 3, 5, 1]. Max heap after heapify: [10, 5, 3, 4, 1].

2. Step 2: Extract max and sort

   Swap 10 with last element, heapify reduced heap: [5, 4, 3, 1, 10]. Repeat until sorted: final sorted array is [1, 3, 4, 5, 10].

3. Final Answer:

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

4. Quick Check:

   Heap sort sorts 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:

void HeapSort(int[] arr) {
  int n = arr.Length;
  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, n, 0);
  }
}

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 swap = arr[i];
    arr[i] = arr[largest];
    arr[largest] = swap;
    Heapify(arr, n, largest);
  }
}

medium

A. Heapify call inside second loop uses wrong size parameter

B. The first for loop should start from n/2, not n/2 - 1

C. The second for loop condition should be i >= 0, not i > 0

D. Swap logic inside Heapify is incorrect

Solution

1. Step 1: Examine the second loop's Heapify call

   After swapping arr[0] and arr[i], the effective heap size is i. However, the code calls Heapify(arr, n, 0), using the original full size n instead of the reduced size i. This is the error.

2. Step 2: Confirm other options are not errors

   The first for loop should start from n/2, not n/2 - 1 is incorrect because it correctly starts at n/2 - 1. The second for loop condition should be i >= 0, not i > 0 is wrong because i > 0 is appropriate. Swap logic inside Heapify is incorrect is false; the swap is correct.

3. Final Answer:

   Heapify call inside second loop uses wrong size parameter -> Option A

4. Quick Check:

   Heapify in extract phase uses reduced size i, not n = B [OK]

Hint: Check loop bounds and heapify size carefully [OK]

Common Mistakes:

• Changing loop start incorrectly
• Using wrong loop end condition
• Misunderstanding heap size in heapify

5. Given a large array with many duplicate values, which modification to the standard heap sort algorithm can improve its stability (preserving order of equal elements)?

hard

A. Use a min heap instead of a max heap

B. Sort the array twice with heap sort

C. Add an index field to elements and compare indices when values are equal

D. Skip heapify calls for duplicate values

Solution

1. Step 1: Understand stability in sorting

   Stability means equal elements keep their original order after sorting.

2. Step 2: Analyze heap sort stability

   Standard heap sort is not stable because heap operations can reorder equal elements arbitrarily.

3. Step 3: Find modification to improve stability

   Adding an index field and comparing indices when values are equal preserves original order, making heap sort stable.

4. Final Answer:

   Add an index field to elements and compare indices when values are equal -> Option C

5. Quick Check:

   Use index to preserve order for stability = D [OK]

Hint: Use original indices to maintain stability in heap sort [OK]

Common Mistakes:

• Thinking min heap makes sort stable
• Skipping heapify breaks heap property
• Sorting twice wastes time without stability