Build Heap from Array Heapify in DSA Typescript - Execution Trace

Concept Flow - Build Heap from Array Heapify

Start with array

↓

Identify last non-leaf node

↓

For each node from last non-leaf to root

↓

Perform heapify on node

↓

Swap with largest child if needed

↓

Repeat heapify down subtree

↓

Move to previous node

↓

All nodes heapified → Heap built

Start from the last non-leaf node and heapify each node upwards to the root, ensuring the heap property is maintained.

Execution Sample

DSA Typescript

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

function heapify(arr: number[], n: number, i: number) {
  let largest = i;
  let left = 2 * i + 1;
  let 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) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

This code builds a max heap from an unsorted array by heapifying nodes 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]	-	4 -> 10 -> 3 -> 5 -> 1
2	Heapify node	1	[4, 10, 3, 5, 1]	left=3 (5 > 10? No), right=4 (1 > 10? No), largest=1	4 -> 10 -> 3 -> 5 -> 1
3	Heapify node	0	[4, 10, 3, 5, 1]	largest=1 (10 > 4), swap arr[0] and arr[1]	10 -> 4 -> 3 -> 5 -> 1
4	Heapify node	1	[10, 4, 3, 5, 1]	largest=3 (5 > 4), swap arr[1] and arr[3]	10 -> 5 -> 3 -> 4 -> 1
5	Heapify node	3	[10, 5, 3, 4, 1]	largest=3 (no children), no swap	10 -> 5 -> 3 -> 4 -> 1
6	End buildHeap	-	[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 2	After Step 3	After Step 4	After Step 5	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]
largest	-	1	1	3	3	-
i	-	1	0	1	3	-
left	-	3	1	3	-	-
right	-	4	2	4	-	-

Key Moments - 3 Insights

Why do we start heapifying from the last non-leaf node and not from the root?

Because leaf nodes have no children to compare with, starting from the last non-leaf node ensures we fix heap property bottom-up, as shown in execution_table rows 2 and 3.

What happens if the largest child is not greater than the current node during heapify?

No swap occurs and heapify stops for that node, as seen in step 5 where largest equals the node itself and no changes happen.

Why do we recursively call heapify after swapping nodes?

Because swapping can break the heap property in the subtree below, so we fix it by heapifying the affected child node, demonstrated in steps 3 and 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the array state after heapifying node 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 the 'Visual State' column at step 3 in execution_table

At which step does the heapify process stop making swaps?

A Step 2

B Step 4

C Step 5

D Step 6

💡 Hint

Look for the step where 'no swap' is mentioned in the 'Pointer Changes' column

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

A No swaps would occur during heapify steps

B Heapify would start from the root instead of last non-leaf

C The array would be reversed

D Heapify would only run once

💡 Hint

Refer to the 'Pointer Changes' column showing swaps in execution_table

Concept Snapshot

Build Heap from Array Heapify:
- Start from last non-leaf node (floor(n/2)-1) down to 0
- For each node, compare with children
- Swap with largest child if needed
- Recursively heapify affected 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 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 max heap property is maintained throughout the array. The execution trace shows the array changing step-by-step, with swaps occurring only when a child is larger than the current node. The process stops when no swaps are needed, resulting in a max heap.