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

Concept Flow - Build Heap from Array Heapify

Start with input array

↓

Identify last non-leaf node

↓

For each node from last non-leaf to root

↓

Perform heapify on current node

↓

Heapify: Compare node with children

↓

Swap with largest child if needed

↓

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 upwards to the root to build a max-heap from the array.

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]	Set i = 1 (n/2 -1)	[4, 10, 3, 5, 1]
2	Heapify at index 1	1	[4, 10, 3, 5, 1]	Compare arr[1]=10 with children arr[3]=5, arr[4]=1	[4, 10, 3, 5, 1]
3	Heapify at index 1	1	[4, 10, 3, 5, 1]	No swap needed (10 is largest)	[4, 10, 3, 5, 1]
4	Move to index 0	0	[4, 10, 3, 5, 1]	Compare arr[0]=4 with children arr[1]=10, arr[2]=3	[4, 10, 3, 5, 1]
5	Swap arr[0] and arr[1]	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 arr[1]=4 with children arr[3]=5, arr[4]=1	[10, 4, 3, 5, 1]
7	Swap arr[1] and arr[3]	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]	No children, stop	[10, 5, 3, 4, 1]
9	All nodes heapified	-	[10, 5, 3, 4, 1]	Heap built	[10, 5, 3, 4, 1]

💡 All non-leaf nodes heapified, max-heap property satisfied for entire array.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	Final
i	-	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	1	3	-

Key Moments - 3 Insights

Why do we start heapify from index n/2 - 1 and not from the last element?

Because nodes from n/2 to n-1 are leaf nodes and already satisfy heap property. See execution_table step 1 where i starts at 1 for n=5.

Why do we heapify again at the child index after swapping?

Swapping may break heap property at the child, so we heapify recursively down. See steps 6-8 where after swapping at index 1, heapify continues at index 3.

What happens if no swap is needed during heapify?

Heapify stops for that node as heap property is satisfied. See step 3 where no swap occurs at index 1.

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

Check the Visual State column at step 5 in execution_table.

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

A Step 6

B Step 8

C Step 7

D Step 9

💡 Hint

Look for 'No children, stop' in the Action column in execution_table.

If the input array was already a max-heap, how would the execution_table change?

A More swaps would occur

B Heapify would start from index 0 instead of n/2 -1

C No swaps would occur during heapify

D Heapify would not be called at all

💡 Hint

Refer to step 3 where no swap is needed when heap property is already satisfied.

Concept Snapshot

Build Heap from Array (Heapify):
- Start from last non-leaf node (n/2 -1) down to root
- For each node, heapify: compare with children
- Swap with largest child if needed
- Repeat heapify down the subtree
- Result: array satisfies max-heap property

Full Transcript

To build a max-heap from an array, we start heapifying from the last non-leaf node, which is at index n/2 -1, moving upwards to the root. Heapify compares the node with its children and swaps with the largest child if needed, then continues heapifying down the subtree. This process ensures the max-heap property is satisfied for the entire array. Leaf nodes do not need heapify. The example array [4, 10, 3, 5, 1] is transformed step-by-step into [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 rearrange elements to satisfy the heap property

D. To reverse the array elements

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 this property holds for every subtree starting from a node.

3. Final Answer:

   To rearrange elements to satisfy the heap property -> Option C

4. Quick Check:

   Heapify = rearrange for heap property [OK]

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

Common Mistakes:

• Thinking heapify sorts the array
• Confusing heapify with finding max 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, i, n);

C. heapify(n, i, arr);

D. heapify(arr, n, i);

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

   heapify(arr, n, i); matches the standard signature: heapify(arr, n, i); others have wrong order.

3. Final Answer:

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

4. Quick Check:

   heapify(arr, size, index) = B [OK]

Hint: Remember: array, size, then index for heapify call [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, 0) assuming a max-heap?

medium

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

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

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

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

Solution

1. Step 1: Identify root and children

   Index 0 has value 4; children at indices 1 and 2 are 10 and 3.

2. Step 2: Swap with largest child and heapify

   Swap 4 with 10 (largest child). Now at index 1, value 4 has children 5 and 1. Swap 4 with 5. Final array: [10, 5, 3, 4, 1]

3. Final Answer:

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

4. Quick Check:

   Max-heap root fixed = [10, 5, 3, 4, 1] [OK]

Hint: Swap root with largest child, then heapify child subtree [OK]

Common Mistakes:

• Not swapping with largest child
• Stopping after first swap
• Confusing min-heap with max-heap

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. Heapify should be called with index i+1

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

C. Loop should run from 0 to n-1

D. No error, code is correct

Solution

1. Step 1: Understand heap building order

   Heap building requires heapify from last non-leaf node down to root, i.e., from n/2 - 1 down to 0.

2. Step 2: Identify loop direction and range error

   The loop incorrectly goes from 0 up to n/2, which is wrong direction and range.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Looping forward instead of backward
• Starting loop at 0 without decrement
• Calling heapify with wrong index

5. You have an array arr = [3, 9, 2, 1, 4, 5]. After building a max heap using the standard heapify method, what is the final array?

hard

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

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

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

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

Solution

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

   Last non-leaf index = n/2 -1 = 2. Heapify at index 2: children 5 and none, 2 < 5, swap to get [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 change.

3. Step 3: Heapify at index 0

   Index 0 value 3, children 9 and 5. Swap 3 with 9: [9,3,5,1,4,2]. Heapify at index 1: value 3, children 1 and 4. Swap 3 with 4: [9,4,5,1,3,2].

4. Final Answer:

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

5. Quick Check:

   Max heap built = [9,4,5,1,3,2] [OK]

Hint: Heapify bottom-up, swap with largest child repeatedly [OK]

Common Mistakes:

• Not heapifying all parents
• Swapping with wrong child
• Stopping heapify early