Build Heap from Array Heapify in DSA Java - 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 on node

↓

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 heap property, resulting in a built heap.

Execution Sample

DSA Java

int[] arr = {4, 10, 3, 5, 1};
for (int i = arr.length / 2 - 1; i >= 0; i--) {
    heapify(arr, arr.length, i);
}
// heapify function swaps to maintain max-heap

Builds a max-heap from an unsorted array by heapifying from last non-leaf node up to root.

Execution Table

Step	Operation	Node Index	Nodes in Array	Pointer Changes	Visual State
1	Start build heap	-	[4, 10, 3, 5, 1]	-	4 -> 10 -> 3 -> 5 -> 1
2	Find last non-leaf node	-	[4, 10, 3, 5, 1]	-	Index = 1 (value 10)
3	Heapify node	1	[4, 10, 3, 5, 1]	Compare 10 with children 5 and 1	4 -> 10 -> 3 -> 5 -> 1 (no swap)
4	Move to previous node	0	[4, 10, 3, 5, 1]	-	Index = 0 (value 4)
5	Heapify node	0	[4, 10, 3, 5, 1]	Compare 4 with children 10 and 3	Swap 4 and 10
6	After swap	0->1	[10, 4, 3, 5, 1]	Heapify at index 1	10 -> 4 -> 3 -> 5 -> 1
7	Heapify node	1	[10, 4, 3, 5, 1]	Compare 4 with children 5 and 1	Swap 4 and 5
8	After swap	1->3	[10, 5, 3, 4, 1]	Heapify at index 3	10 -> 5 -> 3 -> 4 -> 1
9	Heapify node	3	[10, 5, 3, 4, 1]	No children, stop	10 -> 5 -> 3 -> 4 -> 1
10	All nodes heapified	-	[10, 5, 3, 4, 1]	-	Heap built: 10 -> 5 -> 3 -> 4 -> 1

💡 All nodes from last non-leaf to root heapified, heap property satisfied.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
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]
i (node index)	-	1	0	1	-
heapify calls	0	1	2	3	3

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 last non-leaf ensures all subtrees below are heapified first, as shown in execution_table rows 2 and 3.

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

Swapping may break heap property in the subtree below the swapped child. So we heapify recursively on that child to fix it, as seen in steps 6 to 9.

What happens if no swap is needed during heapify?

Heapify stops immediately because the subtree already satisfies heap property, like in step 3 where node 1's children are smaller.

Visual Quiz - 3 Questions

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

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

B [10, 4, 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 because the node has no children?

A Step 9

B Step 3

C Step 7

D Step 10

💡 Hint

Look for 'No children, stop' in the Pointer Changes column.

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

A More swaps would occur

B Heapify would start from root only

C Heapify would stop early with no swaps

D Heapify would not run at all

💡 Hint

Refer to step 3 where no swap happens because heap property holds.

Concept Snapshot

Build Heap from Array Heapify:
- Start from last non-leaf node (index = n/2 -1)
- Move upwards to root, apply heapify
- 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 heapifying from the last non-leaf node up 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 heap property. The execution table shows each step, including swaps and pointer changes, leading to the final heap. Key moments clarify why we start from last non-leaf and why recursive heapify is needed after swaps.

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 is a special tree-based structure 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 so that the heap property is maintained starting from a node down to its children.

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 heap property from a node down [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 start heapifying an array of size n in Java when building a max heap?

easy

A. for (int i = 0; i < n; i++) heapify(arr, i, n);

B. for (int i = n - 1; i >= 0; i--) heapify(arr, i, n);

C. for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, i, n);

D. for (int i = 1; i < n; i++) heapify(arr, i, n);

Solution

1. Step 1: Identify heapify start index

   Heapify starts from the last non-leaf node, which is at index n/2 - 1, moving upwards to root.

2. Step 2: Loop direction and range

   The loop runs backward from n/2 - 1 down to 0 to ensure all subtrees satisfy heap property.

3. Final Answer:

   for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, i, n); -> Option C

4. Quick Check:

   Start heapify at last non-leaf node [OK]

Hint: Start heapify from n/2 - 1 down to 0 [OK]

Common Mistakes:

• Starting heapify from index 0 upwards
• Heapifying leaf nodes unnecessarily
• Looping in wrong direction

3. Given the array [4, 10, 3, 5, 1], what will be the array after building a max heap using heapify?

medium

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

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

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

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

Solution

1. Step 1: Start heapify from index 1 (n/2 - 1)

   Heapify at index 1: children are 5 and 1. Max child is 5. Swap 10 and 5? No, 10 > 5, so no swap.

2. Step 2: Heapify at index 0

   At index 0: value 4, children 10 and 3. Max child is 10. Swap 4 and 10. Array becomes [10, 4, 3, 5, 1]. Now heapify at index 1 again.

3. Step 3: Heapify at index 1 again

   At index 1: value 4, children 5 and 1. Max child is 5. Swap 4 and 5. Array becomes [10, 5, 3, 4, 1].

4. Final Answer:

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

5. Quick Check:

   Max heap built correctly [OK]

Hint: Heapify bottom-up swaps to fix max heap [OK]

Common Mistakes:

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

4. Consider this heapify method snippet in Java:

void heapify(int[] arr, int i, int n) {
  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, largest, n);
  }
}

What is the bug if the method is called with heapify(arr, 0, arr.length - 1)?

medium

A. The size parameter should be arr.length, not arr.length - 1

B. The left and right child calculations are incorrect

C. The recursive call should be heapify(arr, i, n) instead of heapify(arr, largest, n)

D. The swap logic is missing

Solution

1. Step 1: Understand parameter n meaning

   Parameter n represents the size of the array segment to heapify, so it should be the length of the array.

2. Step 2: Identify off-by-one error

   Using arr.length - 1 excludes the last element, causing incorrect heapify behavior and possible index errors.

3. Final Answer:

   The size parameter should be arr.length, not arr.length - 1 -> Option A

4. Quick Check:

   Pass full length for heapify size [OK]

Hint: Pass full array length, not length minus one [OK]

Common Mistakes:

• Passing length - 1 as size
• Miscalculating child indices
• Incorrect recursive call parameters

5. You have an array [3, 9, 2, 1, 4, 5]. After building a max heap using heapify, what will be the array? Also, explain why starting heapify from n/2 - 1 is efficient compared to starting from index 0.

hard

A. [9, 5, 4, 3, 2, 1]; starting from 0 is better for full coverage

B. [9, 4, 5, 1, 3, 2]; starting from n/2 - 1 avoids unnecessary heapify on leaf nodes

C. [5, 9, 4, 3, 2, 1]; starting from n/2 - 1 is inefficient

D. [3, 9, 2, 1, 4, 5]; heapify does not change array order

Solution

1. Step 1: Build max heap from bottom up

   Start heapify at index 2 (n/2 - 1 = 6/2 - 1 = 2): - At index 2 (value 2), children: 5 (index 5), no right child. - Swap 2 and 5 -> [3, 9, 5, 1, 4, 2] Heapify at index 1: - Value 9, children 1 and 4, no swap. Heapify at index 0: - Value 3, children 9 and 5. - Swap 3 and 9 -> [9, 3, 5, 1, 4, 2] Heapify at index 1: - Value 3, children 1 and 4. - Swap 3 and 4 -> [9, 4, 5, 1, 3, 2]

2. Step 2: Explain efficiency of starting at n/2 - 1

   Nodes from n/2 to n-1 are leaf nodes with no children, so heapify on them is unnecessary. Starting at n/2 - 1 reduces calls and improves efficiency.

3. Final Answer:

   [9, 4, 5, 1, 3, 2]; starting from n/2 - 1 avoids unnecessary heapify on leaf nodes -> Option B

4. Quick Check:

   Heapify bottom-up skips leaves for efficiency [OK]

Hint: Heapify from last non-leaf node skips leaves [OK]

Common Mistakes:

• Heapifying leaf nodes unnecessarily
• Incorrect swaps during heapify
• Misunderstanding heapify start index