Build Heap from Array Heapify in DSA C#

Mental Model

We turn an unordered list into a heap by fixing each subtree from the bottom up, ensuring the heap property holds everywhere.

Analogy: Imagine stacking boxes in a pyramid where each box must be larger than the boxes below it; you start fixing from the bottom rows up to the top to make the pyramid stable.

Array: [4, 10, 3, 5, 1]
Index:  0   1   2  3  4
Heap tree:
       4
     /   \
   10     3
  /  \
 5    1

Dry Run Walkthrough

Input: array: [4, 10, 3, 5, 1]

Goal: Convert the array into a max heap where each parent is greater than its children

Step 1: Start heapify at index 1 (value 10), check children at indices 3 and 4

Array: [4, 10, 3, 5, 1]
Heap tree:
       4
     /   \
   10↑    3
  /  \
 5    1

Why: We start from the last non-leaf node to fix subtrees bottom-up

Step 2: Compare 10 with children 5 and 1; 10 is largest, no swap needed

Array: [4, 10, 3, 5, 1]
Heap tree:
       4
     /   \
   10↑    3
  /  \
 5    1

Why: Subtree rooted at index 1 already satisfies heap property

Step 3: Heapify at index 0 (value 4), compare with children 10 and 3

Array: [4↑, 10, 3, 5, 1]
Heap tree:
       4↑
     /   \
   10     3
  /  \
 5    1

Why: Fix the root subtree to maintain heap property

Step 4: Swap 4 with largest child 10 at index 1

Array: [10, 4, 3, 5, 1]
Heap tree:
       10
     /   \
   4↑     3
  /  \
 5    1

Why: Parent must be larger than children, so swap with largest child

Step 5: Heapify at index 1 (value 4), compare with children 5 and 1

Array: [10, 4↑, 3, 5, 1]
Heap tree:
       10
     /   \
   4↑     3
  /  \
 5    1

Why: After swap, fix subtree rooted at index 1

Step 6: Swap 4 with largest child 5 at index 3

Array: [10, 5, 3, 4, 1]
Heap tree:
       10
     /   \
   5     3
  /  \
 4↑   1

Why: Maintain heap property by swapping with largest child

Step 7: Heapify at index 3 (value 4), no children to compare, stop

Array: [10, 5, 3, 4, 1]
Heap tree:
       10
     /   \
   5     3
  /  \
 4     1

Why: Leaf node reached, subtree is heap

Result:

Array: [10, 5, 3, 4, 1]
Heap tree:
       10
     /   \
   5     3
  /  \
 4     1

Annotated Code

DSA C#

using System;

class MaxHeap
{
    private int[] heap;
    private int size;

    public MaxHeap(int[] array)
    {
        heap = array;
        size = array.Length;
        BuildHeap();
    }

    private void BuildHeap()
    {
        // Start from last non-leaf node and heapify each
        for (int i = size / 2 - 1; i >= 0; i--)
        {
            Heapify(i);
        }
    }

    private void Heapify(int i)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        // Check if left child is larger
        if (left < size && heap[left] > heap[largest])
            largest = left;

        // Check if right child is larger
        if (right < size && heap[right] > heap[largest])
            largest = right;

        // If largest is not root, swap and continue heapifying
        if (largest != i)
        {
            int temp = heap[i];
            heap[i] = heap[largest];
            heap[largest] = temp;

            Heapify(largest);
        }
    }

    public void PrintHeap()
    {
        for (int i = 0; i < size; i++)
        {
            Console.Write(heap[i]);
            if (i < size - 1) Console.Write(" -> ");
        }
        Console.WriteLine(" -> null");
    }
}

class Program
{
    static void Main()
    {
        int[] array = {4, 10, 3, 5, 1};
        MaxHeap maxHeap = new MaxHeap(array);
        maxHeap.PrintHeap();
    }
}

for (int i = size / 2 - 1; i >= 0; i--)

start heapify from last non-leaf node up to root

Heapify(i);

fix subtree rooted at index i to maintain heap property

if (left < size && heap[left] > heap[largest]) largest = left;

find largest among root and left child

if (right < size && heap[right] > heap[largest]) largest = right;

find largest among current largest and right child

if (largest != i) { swap and Heapify(largest); }

swap root with largest child and recursively heapify affected subtree

Output

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

Complexity Analysis

Time: O(n) because heapify is called on n/2 nodes and each call takes O(log n) in worst case, but overall build heap is linear due to decreasing subtree sizes

Space: O(1) because heapify is done in place without extra arrays

vs Alternative: Naive approach inserting elements one by one into heap is O(n log n), so build heap via heapify is more efficient

Edge Cases

Empty array

No heapify calls as the loop doesn't run, PrintHeap outputs " -> null"

DSA C#

for (int i = size / 2 - 1; i >= 0; i--)

Single element array

No heapify calls as size/2 - 1 = -1 < 0 so loop skips, single element is trivially a valid heap

DSA C#

for (int i = size / 2 - 1; i >= 0; i--)

All elements equal

No swaps occur, heap property already holds

DSA C#

if (largest != i)

When to Use This Pattern

When you need to build a heap from an unordered array efficiently, use the bottom-up heapify approach because it fixes subtrees starting from the bottom, making the process faster than inserting elements one by one.

Common Mistakes

Mistake: Starting heapify from the root instead of the last non-leaf node
Fix: Start heapify from index size/2 - 1 down to 0 to ensure all subtrees are fixed

Mistake: Not recursively heapifying after a swap
Fix: After swapping, call heapify recursively on the affected child to maintain heap property

Summary

Builds a max heap from an unordered array by fixing subtrees from bottom up.

Use when you want to efficiently convert an array into a heap for heap operations.

The key insight is starting heapify from the last non-leaf node ensures all subtrees become heaps.

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