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.