Build Heap from Array Heapify in DSA Go - 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

↓

Done when root is heapified

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

Execution Sample

DSA Go

arr := []int{4, 10, 3, 5, 1}
for i := len(arr)/2 - 1; i >= 0; i-- {
    heapify(arr, len(arr), i)
}

Build a max heap from the array by heapifying 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	-	[4, 10, 3, 5, 1]	-	[4, 10, 3, 5, 1]
2	Find last non-leaf node	-	[4, 10, 3, 5, 1]	lastNonLeaf = 1	[4, 10, 3, 5, 1]
3	Heapify node	1	[4, 10, 3, 5, 1]	Compare 10 with children 5 and 1	[4, 10, 3, 5, 1]
4	Heapify node	0	[4, 10, 3, 5, 1]	Compare 4 with children 10 and 3	Swap 4 and 10 -> [10, 4, 3, 5, 1]
5	Heapify node	1	[10, 4, 3, 5, 1]	Compare 4 with children 5 and 1	Swap 4 and 5 -> [10, 5, 3, 4, 1]
6	Heapify node	3	[10, 5, 3, 4, 1]	Compare 4 with children (none)	No swap -> [10, 5, 3, 4, 1]
7	Done	-	[10, 5, 3, 4, 1]	-	[10, 5, 3, 4, 1]

💡 All non-leaf nodes heapified, array satisfies max heap property

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	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]	[10, 5, 3, 4, 1]
lastNonLeaf	-	1	1	1	1	1
currentNode	-	1	0	1	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, they already satisfy heap property. Starting from last non-leaf ensures all subtrees below are heapified before moving up, as shown in steps 3 and 4.

Why do we heapify the child node again after swapping?

Swapping can break heap property in the subtree rooted at the child. So we heapify the child node again to fix this, as seen in steps 5 and 6.

What happens if no swap is needed during heapify?

Heapify stops for that node because the subtree already satisfies the heap property, like in step 6 where no swap occurs.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after heapifying node at index 0?

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

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

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

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

💡 Hint

Check Step 6 in the execution table for the array after fully heapifying node 0.

At which step does the condition to heapify the child node after swap occur?

A Step 3

B Step 4

C Step 5

D Step 7

💡 Hint

Look at the operation column where heapify is applied again on node 1 after a swap.

If the initial array was already a max heap, how would the visual state change during heapify?

A Multiple swaps would occur

B No swaps would occur, array stays the same

C Array would become sorted ascending

D Heapify would not run at all

💡 Hint

Refer to step 6 where no swap means heap property is already satisfied.

Concept Snapshot

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

Full Transcript

To build a heap from an array, we start from the last non-leaf node and move upwards to the root. At each node, we apply heapify, which compares the node with its children and swaps with the largest child if needed. After swapping, heapify is applied again on the child node to maintain heap property. This process continues until the root is heapified. The final array represents a max heap where each parent node 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 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 to ensure this property holds for every subtree starting from a given 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:

• Confusing heapify with sorting
• Thinking heapify finds max element only
• Assuming heapify reverses array

2. Which of the following is the correct way to call heapify on a node index i in Go when building a max heap from an array arr of size n?

easy

A. heapify(n, arr, i)

B. heapify(i, arr, n)

C. heapify(arr, i, n)

D. heapify(arr, n, i)

Solution

1. Step 1: Understand heapify function parameters

   Heapify usually takes the array, size of heap, and the index to heapify as parameters in that order.

2. Step 2: Match parameter order

   heapify(arr, n, i) matches the correct order: array, size, index.

3. Final Answer:

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

4. Quick Check:

   heapify(arr, n, i) is correct call [OK]

Hint: Remember: heapify(array, size, index) [OK]

Common Mistakes:

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

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

medium

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

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

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

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

Solution

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

   Last non-leaf node index = n/2 -1 = 6/2 -1 = 2. Heapify nodes 2, 1, 0 in order.

2. Step 2: Heapify index 2

   Node 2 value=2, children 5 (index 5). Swap 2 and 5. Array becomes [3, 9, 5, 1, 4, 2].

3. Step 3: Heapify index 1

   Node 1 value=9, children 1 and 4. 9 is largest, no change.

4. Step 4: Heapify index 0

   Node 0 value=3, children 9 and 5. Swap 3 and 9. Array becomes [9, 3, 5, 1, 4, 2]. Heapify index 1 again: 3 with children 1 and 4, swap 3 and 4. Final array: [9, 4, 5, 1, 3, 2].

5. Final Answer:

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

6. Quick Check:

   Bottom-up heapify gives [9,4,5,1,3,2] [OK]

Hint: Heapify bottom-up swaps to fix largest child first [OK]

Common Mistakes:

• Not heapifying children after swap
• Starting heapify from wrong index
• Confusing max-heap with min-heap

4. Consider this Go code snippet to build a max heap from array arr. What is the error?

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

medium

A. heapify function is missing the array size parameter

B. The loop should start from n/2 - 1, not n/2

C. The loop should increment i, not decrement

D. The loop condition should be i > 0, not i >= 0

Solution

1. Step 1: Identify correct start index for heapify

   Heapify starts from last non-leaf node at index n/2 - 1, not n/2.

2. Step 2: Analyze loop range

   Starting at n/2 includes one extra index which is a leaf node, unnecessary and may cause incorrect behavior.

3. Final Answer:

   The loop should start from n/2 - 1, not n/2 -> Option B

4. Quick Check:

   Start heapify at n/2 - 1 [OK]

Hint: Start heapify at last non-leaf node: n/2 - 1 [OK]

Common Mistakes:

• Starting loop at n/2 instead of n/2 - 1
• Loop increment instead of decrement
• Wrong loop condition excluding index 0

5. You have an array [4, 10, 3, 5, 1]. After building a max heap using heapify, you want to insert a new element 15 and maintain the max heap property. Which sequence of operations correctly maintains the heap?

hard

A. Append 15, then bubble up the new element until heap property is restored

B. Append 15, then heapify only the root node

C. Append 15, then heapify from last non-leaf node down to root

D. Replace root with 15, then heapify entire array

Solution

1. Step 1: Understand insertion in heap

   To insert, add element at end, then restore heap by bubbling up (swapping with parent if larger).

2. Step 2: Why bubble up?

   Heapify from bottom up is for building heap initially; for insertion, bubbling up fixes heap efficiently.

3. Final Answer:

   Append 15, then bubble up the new element until heap property is restored -> Option A

4. Quick Check:

   Insert + bubble up maintains heap [OK]

Hint: Insert at end, bubble up to fix heap [OK]

Common Mistakes:

• Using heapify from root after insertion
• Heapifying only root node
• Replacing root without adjusting heap