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

↓

Heapify node

↓

Compare node with children

↓

Swap if child larger (max-heap)

↓

Repeat heapify down subtree

↓

Move to previous node

↓

Done when root heapified

Start from the last non-leaf node and heapify each node up to the root to build a max-heap.

Execution Sample

DSA Javascript

function buildHeap(arr) {
  let n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
}

function heapify(arr, n, i) {
  // heapify logic here
}

Builds a max-heap from an unsorted array by heapifying nodes from bottom up.

Execution Table

Step	Operation	Node Index	Nodes in Array	Pointer Changes	Visual State
1	Start buildHeap	-	[4, 10, 3, 5, 1]	-	4 -> 10 -> 3 -> 5 -> 1
2	Find last non-leaf node	-	-	-	Last non-leaf index = 1
3	Heapify node	1	[4, 10, 3, 5, 1]	Compare arr[1]=10 with children arr[3]=5 and arr[4]=1	4 -> 10 -> 3 -> 5 -> 1
4	Heapify node	0	[4, 10, 3, 5, 1]	Compare arr[0]=4 with children arr[1]=10 and 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 node	1	[10, 4, 3, 5, 1]	Compare arr[1]=4 with children arr[3]=5 and 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 node	3	[10, 5, 3, 4, 1]	Node 3 is leaf, no action	10 -> 5 -> 3 -> 4 -> 1
9	BuildHeap done	-	[10, 5, 3, 4, 1]	-	10 -> 5 -> 3 -> 4 -> 1

💡 All non-leaf nodes heapified, array is now a max-heap.

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 (heapify index)	-	1	0	1	-
n (array length)	5	5	5	5	5

Key Moments - 3 Insights

Why do we start heapifying from the last non-leaf node instead of the root?

Because leaf nodes have no children to compare with, starting from the last non-leaf node ensures we heapify all subtrees bottom-up, as shown in steps 2 and 3.

Why do we swap nodes during heapify?

We swap to maintain the max-heap property where parent nodes are larger than children, as seen in steps 5 and 7 where swaps happen to move larger values up.

What happens if a node is a leaf during heapify?

No action is needed because leaf nodes have no children to compare with, as shown in step 8.

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 the execution_table.

At which step does the heapify process swap the values 4 and 5?

A Step 4

B Step 7

C Step 6

D Step 8

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns around steps 6 and 7.

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

A Heapify would start from the root only.

B More swaps would occur to fix the heap.

C No swaps would occur during heapify steps.

D The array size would change.

💡 Hint

Refer to the 'Swap' actions in the 'Pointer Changes' column in the execution_table.

Concept Snapshot

Build Heap from Array Heapify:
- Start from last non-leaf node (floor(n/2)-1)
- Heapify each node up to root
- Heapify compares node with children
- Swap if child larger (max-heap)
- Repeat heapify down subtree
- Result: array represents a max-heap

Full Transcript

To build a max-heap from an array, we start heapifying from the last non-leaf node moving up to the root. Heapify compares a node with its children and swaps if a child is larger to maintain the max-heap property. This process repeats down the subtree until the heap property is restored. Leaf nodes are skipped since they have no children. After all non-leaf nodes are heapified, the array represents a max-heap.