Build Heap from Array Heapify in DSA C - Execution Trace

Concept Flow - Build Heap from Array Heapify

Start with array

↓

Find last non-leaf node

↓

For each node from last non-leaf to root

↓

Apply heapify

↓

Swap node with largest child if needed

↓

Repeat heapify on swapped child

↓

Move to previous node

↓

All nodes heapified -> Heap built

Start from the last non-leaf node and move upwards, applying heapify to ensure each subtree satisfies the heap property, resulting in a complete heap.

Execution Sample

DSA C

void buildHeap(int arr[], int n) {
  for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
}

This code builds a max heap from an unsorted array by calling heapify from the last non-leaf node up to the root.

Execution Table

Step	Operation	Node Index	Nodes in Array	Pointer Changes	Visual State
1	Start buildHeap	-	[4, 10, 3, 5, 1]	i = 1 (last non-leaf)	[4, 10, 3, 5, 1]
2	heapify at i=1	1	[4, 10, 3, 5, 1]	Compare node 1 with children 3 and 4	[4, 10, 3, 5, 1]
3	No swap needed	1	[4, 10, 3, 5, 1]	10 > 5 and 1	[4, 10, 3, 5, 1]
4	Move to i=0	0	[4, 10, 3, 5, 1]	i-- to 0	[4, 10, 3, 5, 1]
5	heapify at i=0	0	[4, 10, 3, 5, 1]	Compare node 0 with children 1 and 2	[4, 10, 3, 5, 1]
6	Swap node 0 and child 1	0 -> 1	[4, 10, 3, 5, 1]	Swap 4 and 10	[10, 4, 3, 5, 1]
7	heapify at i=1	1	[10, 4, 3, 5, 1]	Compare node 1 with children 3 and 4	[10, 4, 3, 5, 1]
8	Swap node 1 and child 3	1 -> 3	[10, 4, 3, 5, 1]	Swap 4 and 5	[10, 5, 3, 4, 1]
9	heapify at i=3	3	[10, 5, 3, 4, 1]	No children, stop	[10, 5, 3, 4, 1]
10	All nodes heapified	-	[10, 5, 3, 4, 1]	-	[10, 5, 3, 4, 1]

💡 All nodes from last non-leaf to root heapified, array satisfies max heap property

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 8	Final
i	n / 2 - 1 = 1	1	0	0	-
arr	[4, 10, 3, 5, 1]	[4, 10, 3, 5, 1]	[10, 4, 3, 5, 1]	[10, 5, 3, 4, 1]	[10, 5, 3, 4, 1]
heapify node	-	1	0	1	3

Key Moments - 3 Insights

Why do we start heapify from the last non-leaf node (n/2 - 1) and not from the root?

Because leaf nodes have no children and already satisfy heap property. Starting from last non-leaf ensures all subtrees below are heapified before moving up, as shown in steps 1 and 2.

Why do we call heapify recursively after swapping a node with its child?

Swapping can break heap property in the subtree below the swapped child. Recursive heapify fixes this, as seen in steps 6, 7, 8, and 9.

Why does the heapify stop when the node has no children?

Because a node without children cannot violate heap property. This is shown in step 9 where heapify stops at leaf nodes.

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

Check the 'Visual State' column at step 3 in the execution_table.

At which step does the heapify process start at the root node (index 0)?

A Step 2

B Step 5

C Step 6

D Step 8

💡 Hint

Look at the 'Node Index' column to find when i=0 is processed.

If the initial array was already a max heap, how would the execution table change?

A Heapify would start from root only

B More swaps would occur to fix the heap

C No swaps would occur, visual state remains same in all steps

D Heapify would not be called at all

💡 Hint

Refer to the 'Operation' and 'Visual State' columns to see when swaps happen.

Concept Snapshot

Build Heap from Array Heapify:
- Start from last non-leaf node (n/2 - 1) down to root
- Apply heapify at each node
- Heapify swaps node with largest child if needed
- Recursively heapify swapped child
- Result: array satisfies max heap property

Full Transcript

To build a heap from an array, we start heapify from the last non-leaf node, moving upwards to the root. Heapify compares a node with its children and swaps with the largest child if needed, then recursively heapifies the affected subtree. This process ensures the entire array satisfies the max heap property. Leaf nodes are skipped since they have no children. The example array [4, 10, 3, 5, 1] is transformed step-by-step into a max heap [10, 5, 3, 4, 1].

Practice

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

easy

A. To find the maximum element in the array

B. To sort the array in ascending order

C. To reverse the array elements

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

Solution

1. Step 1: Understand heap property

   A heap is a special tree where each parent node is greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role of heapify

   Heapify rearranges elements so the heap property holds for every subtree, starting from the bottom.

3. Final Answer:

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

4. Quick Check:

   Heapify = Rearrange for heap property [OK]

Hint: Heapify fixes subtree order to build a heap fast [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 heapify on an array arr of size n starting from index i in C?

easy

A. heapify(i, arr, n);

B. heapify(arr, n, i);

C. heapify(n, arr, i);

D. heapify(arr, i, n);

Solution

1. Step 1: Understand heapify parameters

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

2. Step 2: Match correct syntax

   Calling heapify(arr, n, i); matches the standard parameter order: array, size, index.

3. Final Answer:

   heapify(arr, n, i); -> Option B

4. Quick Check:

   Function call order = arr, size, index [OK]

Hint: Remember: array first, then size, then index [OK]

Common Mistakes:

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

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

medium

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

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

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

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

Solution

1. Step 1: Identify children of index 1

   Index 1 has children at indices 3 and 4 with values 5 and 1.

2. Step 2: Compare and swap if needed

   Value at index 1 is 10, which is greater than both children, so no swap needed.

3. Final Answer:

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

4. Quick Check:

   Parent >= children, no change [OK]

Hint: Check parent vs children, swap only if smaller [OK]

Common Mistakes:

• Swapping when parent is already largest
• Mixing up child indices
• Assuming heapify sorts entire array

4. Consider this code snippet to build a max heap from array arr of size n. Identify the error:

for (int i = 0; i <= n/2; i++) {
    heapify(arr, n, i);
}

medium

A. Loop should start from n/2 - 1 and go down to 0

B. Loop should start from 0 and go to n - 1

C. heapify function parameters are incorrect

D. No error, code is correct

Solution

1. Step 1: Understand heap building order

   Heap building starts from last non-leaf node at index n/2 - 1 down to 0.

2. Step 2: Check loop direction and range

   Loop incorrectly goes up from 0 to n/2, should go down from n/2 - 1 to 0.

3. Final Answer:

   Loop should start from n/2 - 1 and go down to 0 -> Option A

4. Quick Check:

   Build heap loops down from n/2-1 [OK]

Hint: Build heap loops backward from last parent [OK]

Common Mistakes:

• Looping forward instead of backward
• Starting loop at 0 without going down
• Incorrect heapify parameters

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

hard

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

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

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

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

Solution

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

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

2. Step 2: Heapify at index 1

   Index 1 value 9, children 1 and 4. 9 is largest, no swap -> [3,9,5,1,4,2]

3. Step 3: Heapify at index 0

   Index 0 value 3, children 9 and 5. Largest is 9 at index 1, swap -> [9,3,5,1,4,2]. Heapify at index 1 again: 3 with children 1 and 4, largest is 4 at index 4, swap -> [9,4,5,1,3,2]

4. Final Answer:

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

5. Quick Check:

   Bottom-up heapify fixes subtree order [OK]

Hint: Heapify bottom-up swaps parents with largest child [OK]

Common Mistakes:

• Not heapifying children after swap
• Swapping with wrong child
• Stopping heapify too early