Build Heap from Array Heapify in DSA C# - Execution Trace

Concept Flow - Build Heap from Array Heapify

Start with array

↓

Identify last non-leaf node

↓

For each node from last non-leaf to root

↓

Apply heapify on node

↓

Swap if child > node

↓

Repeat heapify on swapped child

↓

Move to previous node

↓

All nodes heapified -> Max-Heap built

Start from the last non-leaf node and heapify each node up to the root to build a max-heap.

Execution Sample

DSA C#

int[] arr = {4, 10, 3, 5, 1};
BuildHeap(arr);
// After build, arr is a max-heap

Build a max-heap from the given array using heapify from bottom up.

Execution Table

Step	Operation	Node Index	Nodes in Array	Pointer Changes	Visual State
1	Start	-	[4, 10, 3, 5, 1]	heapify start at index 1	[4, 10, 3, 5, 1]
2	Heapify at index 1	1	[4, 10, 3, 5, 1]	Compare node 10 with children 5 and 1	[4, 10, 3, 5, 1]
3	Heapify at index 1	1	[4, 10, 3, 5, 1]	No swap needed (10 > children)	[4, 10, 3, 5, 1]
4	Heapify at index 0	0	[4, 10, 3, 5, 1]	Compare node 4 with children 10 and 3	[4, 10, 3, 5, 1]
5	Swap	0 <-> 1	[4, 10, 3, 5, 1]	Swap 4 and 10	[10, 4, 3, 5, 1]
6	Heapify at index 1	1	[10, 4, 3, 5, 1]	Compare node 4 with children 5 and 1	[10, 4, 3, 5, 1]
7	Swap	1 <-> 3	[10, 4, 3, 5, 1]	Swap 4 and 5	[10, 5, 3, 4, 1]
8	Heapify at index 3	3	[10, 5, 3, 4, 1]	Node 4 has no children, stop	[10, 5, 3, 4, 1]
9	End	-	[10, 5, 3, 4, 1]	All nodes heapified	[10, 5, 3, 4, 1]

💡 Heapify completed for all non-leaf nodes, array is now a max-heap.

Variable Tracker

Variable	Start	After Step 5	After Step 7	Final
arr	[4, 10, 3, 5, 1]	[10, 4, 3, 5, 1]	[10, 5, 3, 4, 1]	[10, 5, 3, 4, 1]
currentIndex	-	0	1	-
leftChildIndex	-	1	3	-
rightChildIndex	-	2	4	-

Key Moments - 3 Insights

Why do we start heapify from the last non-leaf node and not from the root?

Because leaf nodes have no children, so heapify on them does nothing. Starting from the last non-leaf node ensures all subtrees are heapified before reaching the root, as shown in steps 1 and 4.

Why do we heapify again on the child node after swapping?

After swapping, the subtree rooted at the child might violate heap property. So we heapify recursively on that child to fix the heap, as seen in steps 6 and 8.

What happens if no swap is needed during heapify?

Heapify stops for that node because the heap property is satisfied. For example, at step 3, node 10 is already larger than its children, so no swap occurs.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after step 5?

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

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

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

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

💡 Hint

Check the Visual State column at step 5 in the execution_table.

At which step does the heapify process stop for the node at index 3?

A Step 8

B Step 6

C Step 7

D Step 9

💡 Hint

Look for the step where node 4 has no children and heapify stops.

If the initial array was already a max-heap, which step would show no swaps?

A Step 7

B Step 5

C Step 3

D Step 9

💡 Hint

Refer to the step where heapify compares node 10 with its children and no swap occurs.

Concept Snapshot

Build Heap from Array Heapify:
- Start heapify from last non-leaf node to root
- Compare node with children, swap if child is larger
- Recursively heapify swapped child
- After all heapify calls, array is a max-heap
- Time complexity: O(n)

Full Transcript

To build a max-heap from an array, we start heapify from the last non-leaf node going up to the root. Heapify compares a node with its children and swaps if a child is larger, then recursively heapifies the swapped child. This process ensures the heap property is maintained throughout the tree. The example array [4, 10, 3, 5, 1] is transformed step-by-step into [10, 5, 3, 4, 1]. Key points include starting from the last non-leaf node because leaves are already heaps, and recursively heapifying after swaps to fix subtrees. The final array represents a max-heap where each parent is larger than its children.

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