Build Heap from Array Heapify in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output array after building a max heap?

Given the array [3, 9, 2, 1, 4, 5], what is the array representation after applying the build max heap process?

DSA C#

int[] arr = {3, 9, 2, 1, 4, 5};
BuildMaxHeap(arr);
Console.WriteLine(string.Join(", ", arr));

A [9, 4, 5, 1, 3, 2]

B [9, 4, 5, 3, 1, 2]

C [5, 4, 3, 1, 9, 2]

D [9, 3, 5, 1, 4, 2]

💡 Hint

Remember that build max heap starts heapifying from the last non-leaf node upwards.

The build max heap process rearranges the array so that each parent node is greater than its children. Starting from the last non-leaf node, heapify is applied upwards. The final array after heapify is [9, 4, 5, 1, 3, 2].

❓ Predict Output

intermediate

What is the output array after building a min heap?

Given the array [7, 2, 6, 3, 9, 1], what is the array representation after applying the build min heap process?

DSA C#

int[] arr = {7, 2, 6, 3, 9, 1};
BuildMinHeap(arr);
Console.WriteLine(string.Join(", ", arr));

A [1, 2, 3, 7, 9, 6]

B [2, 3, 1, 6, 7, 9]

C [1, 3, 2, 6, 7, 9]

D [1, 2, 6, 3, 9, 7]

💡 Hint

Build min heap ensures each parent is smaller than its children, starting from last non-leaf node.

Applying build min heap rearranges the array so parents are smaller than children. The final array is [1, 2, 3, 7, 9, 6].

🔧 Debug

advanced

Identify the error in this heapify implementation

What error will this C# code cause when building a max heap from an array?

DSA C#

void MaxHeapify(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;
        MaxHeapify(arr, n, largest);
    }
}

void BuildMaxHeap(int[] arr) {
    int n = arr.Length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        MaxHeapify(arr, n, i);
    }
}

A No error, code runs correctly

B StackOverflowException due to infinite recursion

C IndexOutOfRangeException due to invalid array access

D Compilation error due to missing return type

💡 Hint

Check the loop boundary in BuildMaxHeap for correctness.

The for loop in BuildMaxHeap starts at n/2 and goes down to 0 inclusive. But it should start at n/2 - 1. Because of this, the loop runs one extra time with i = n/2, which is a leaf node index, causing MaxHeapify to recurse infinitely on some inputs, leading to StackOverflowException.

❓ Predict Output

advanced

What is the heap array after partial heapify?

Given the array [10, 15, 20, 17, 25], what is the array after calling MaxHeapify on index 1 only?

DSA C#

int[] arr = {10, 15, 20, 17, 25};
MaxHeapify(arr, arr.Length, 1);
Console.WriteLine(string.Join(", ", arr));

A [10, 15, 20, 17, 25]

B [10, 20, 25, 17, 15]

C [10, 25, 20, 17, 15]

D [25, 15, 20, 17, 10]

💡 Hint

MaxHeapify swaps the node with the largest child and continues heapifying down.

At index 1, the children are at indices 3 and 4 with values 17 and 25. The largest child is 25 at index 4. Swap 15 and 25. Then heapify index 4 which is a leaf, so stop. Result: [10, 25, 20, 17, 15].

🧠 Conceptual

expert

Why does build heap run in O(n) time, not O(n log n)?

Which explanation best describes why the build heap algorithm runs in linear time O(n) instead of O(n log n)?

A Because build heap uses a special data structure that reduces heapify cost to constant time

B Because heapify is called only on leaf nodes which take constant time each

C Because build heap only heapifies the root node once

D Because the number of nodes at each level decreases exponentially, and heapify cost per node is proportional to height, summing to O(n)

💡 Hint

Consider how many nodes are at each level and how much work heapify does per node.

Build heap calls heapify starting from the last non-leaf nodes up to the root. Nodes near the bottom have small heights and many nodes, nodes near the top have larger heights but fewer nodes. The total work sums to O(n) because the work per level times number of nodes per level sums linearly.

Practice

1. What is the main purpose of the heapify process when building a heap from an array?

easy

A. To rearrange the array elements to satisfy the heap property

B. To sort the array in ascending order

C. To find the maximum element in the array

D. To reverse the array elements

Solution

1. Step 1: Understand heap property

   A heap must satisfy the heap property where each parent node is greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role of heapify

   The heapify process rearranges elements to ensure this property holds for every subtree starting from a node.

3. Final Answer:

   To rearrange the array elements to satisfy the heap property -> Option A

4. Quick Check:

   Heapify = Rearrange for heap property [OK]

Hint: Heapify fixes subtree to maintain heap order [OK]

Common Mistakes:

• Thinking heapify sorts the array
• Confusing heapify with finding max/min element
• Assuming heapify reverses the array

2. Which of the following is the correct way to call the Heapify method in C# for an array arr of size n at index i?

easy

A. Heapify(arr, n, i);

B. Heapify(i, arr, n);

C. Heapify(n, i, arr);

D. Heapify(arr, i, n);

Solution

1. Step 1: Check method signature

   Heapify usually takes the array, its size, and the index to heapify as parameters in that order.

2. Step 2: Match parameters order

   Heapify(arr, n, i); matches the correct order: array, size, index.

3. Final Answer:

   Heapify(arr, n, i); -> Option A

4. Quick Check:

   Heapify(arr, n, i) correct call [OK]

Hint: Remember parameter order: array, size, index [OK]

Common Mistakes:

• Mixing parameter order
• Passing index before array
• Confusing size and index positions

3. Given the array [4, 10, 3, 5, 1], what will be the array after calling Heapify(arr, 5, 1) assuming a max-heap?

medium

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

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

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

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

Solution

1. Step 1: Identify node at index 1

   Value is 10, children at indices 3 (5) and 4 (1).

2. Step 2: Check heap property

   10 is greater than both children, so no swaps needed.

3. Final Answer:

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

4. Quick Check:

   Parent 10 > children 5,1 so unchanged [OK]

Hint: Check parent vs children values before swapping [OK]

Common Mistakes:

• Swapping when parent is already largest
• Confusing indices of children
• Assuming heapify sorts entire array

4. Consider this code snippet for heapify in 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);
  }
}

What is the bug if the recursive call is missing?

medium

A. Stack overflow error will occur

B. Array will be sorted incorrectly

C. No bug, code works fine

D. Heap property may not be restored in subtrees

Solution

1. Step 1: Understand recursive call role

   After swapping, heapify must be called on the affected child subtree to fix heap property there.

2. Step 2: Effect of missing recursion

   Without recursion, only the root node is fixed, subtrees may remain invalid heaps.

3. Final Answer:

   Heap property may not be restored in subtrees -> Option D

4. Quick Check:

   Missing recursion breaks heap property below swapped node [OK]

Hint: Always recurse after swap to fix subtree [OK]

Common Mistakes:

• Assuming one swap fixes entire heap
• Thinking missing recursion causes crash
• Ignoring subtree heap violations

5. You have the array [3, 9, 2, 1, 4, 5]. After building a max-heap using the heapify method from the bottom up, what is the final array?

hard

A. [9, 4, 5, 3, 1, 2]

B. [9, 4, 5, 1, 3, 2]

C. [9, 3, 5, 1, 4, 2]

D. [9, 5, 4, 3, 1, 2]

Solution

1. Step 1: Start heapify from last non-leaf node

   Last non-leaf node index = (6/2)-1 = 2. Heapify at index 2 (value 2): children 5 (index 5), no right child. Swap 2 and 5 -> [3,9,5,1,4,2]

2. Step 2: Heapify at index 1 (value 9)

   Children 1 (index 3), 4 (index 4). 9 is largest, no change -> [3,9,5,1,4,2]

3. Step 3: Heapify at index 0 (value 3)

   Children 9 (index 1), 5 (index 2). Largest is 9, swap 3 and 9 -> [9,3,5,1,4,2]. Now heapify at index 1 (value 3): children 1 and 4. Largest is 4, swap 3 and 4 -> [9,4,5,1,3,2]

4. Final Answer:

   [9, 4, 5, 1, 3, 2] -> Option B

5. Quick Check:

   Bottom-up heapify gives max-heap [OK]

Hint: Heapify bottom-up from last non-leaf node [OK]

Common Mistakes:

• Not heapifying all non-leaf nodes
• Swapping incorrectly with children
• Stopping heapify too early