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.

Practice

1. What is the main purpose of the heapify process when building a heap from an array?

easy

A. To find the maximum element in the array

B. To sort the array in ascending order

C. To reverse the array elements

D. To rearrange the array elements to satisfy the heap property

Solution

1. Step 1: Understand heap property

   A heap is a special tree where parent nodes follow a specific order compared to children (max-heap or min-heap).

2. Step 2: Role of heapify

   Heapify rearranges elements so that the heap property holds for every subtree, starting from the bottom.

3. Final Answer:

   To rearrange the array elements to satisfy the heap property -> Option D

4. Quick Check:

   Heapify = Rearrange for heap property [OK]

Hint: Heapify fixes order to build a valid heap fast [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 TypeScript syntax to start heapifying from the last non-leaf node in an array arr of length n?

easy

A. for(let i = Math.floor(n / 2); i < n; i++) { heapify(arr, n, i); }

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

C. for(let i = n - 1; i >= 0; i--) { heapify(arr, n, i); }

D. for(let i = 0; i < n; i++) { heapify(arr, n, i); }

Solution

1. Step 1: Identify last non-leaf node index

   In a heap array, last non-leaf node is at index Math.floor(n/2) - 1.

2. Step 2: Loop from last non-leaf to root

   We heapify from this index down to 0 to ensure all subtrees satisfy heap property.

3. Final Answer:

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

4. Quick Check:

   Start heapify at last non-leaf node [OK]

Hint: Start heapify at Math.floor(n/2)-1 down to 0 [OK]

Common Mistakes:

• Starting heapify from 0 upwards
• Starting heapify from last element
• Looping beyond last non-leaf node

3. Given the array arr = [3, 9, 2, 1, 4, 5], what is the array after building a max-heap using heapify?

medium

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

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

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

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

Solution

1. Step 1: Start heapify from index 2 (Math.floor(6/2)-1)

   Heapify at index 2: children 5 (index 5), swap 2 and 5 to get [3,9,5,1,4,2].

2. Step 2: Heapify at index 1 and 0

   Index 1: children 1 and 4, max is 9 at index 1, no swap. Index 0: children 9 and 5, swap 3 and 9. Final array: [9,4,5,1,3,2]

3. Final Answer:

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

4. Quick Check:

   Max-heap root is 9, children smaller [OK]

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

Common Mistakes:

• Not swapping correctly during heapify
• Confusing min-heap with max-heap
• Leaving original array unchanged

4. Consider this TypeScript code snippet to build a max heap:

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);
  }
}

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

What is the error in this code?

medium

A. The loop in buildHeap should run from Math.floor(n/2)-1 down to 0

B. The heapify function swaps elements incorrectly

C. The left and right child indices are calculated wrongly

D. The buildHeap function should not call heapify

Solution

1. Step 1: Analyze buildHeap loop range

   The loop runs from 0 up to Math.floor(n/2), but heapify must start from last non-leaf node down to root.

2. Step 2: Correct loop direction and range

   Loop should be: for(let i = Math.floor(n/2) - 1; i >= 0; i--) to ensure all subtrees heapify properly.

3. Final Answer:

   The loop in buildHeap should run from Math.floor(n/2)-1 down to 0 -> Option A

4. Quick Check:

   Heapify bottom-up loop direction matters [OK]

Hint: Loop heapify bottom-up from last non-leaf node [OK]

Common Mistakes:

• Looping heapify top-down instead of bottom-up
• Incorrect child index calculations
• Not swapping elements during heapify

5. You have an array arr = [4, 10, 3, 5, 1, 2]. After building a min-heap using heapify, what will be the array representation?

hard

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

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

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

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

Solution

1. Step 1: Build min-heap bottom-up

   Start heapify from index 2 (Math.floor(6/2)-1): heapify at index 2 swaps 3 and 2 to get [4,10,2,5,1,3].

2. Step 2: Heapify at index 1 and 0

   At index 1: children 5 and 1, swap 10 and 1 -> [4,1,2,5,10,3]. At index 0: children 1 and 2, swap 4 and 1 -> [1,4,2,5,10,3].

3. Final Answer:

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

4. Quick Check:

   Min-heap root is smallest element 1 [OK]

Hint: Min-heap root is smallest; heapify swaps bottom-up [OK]

Common Mistakes:

• Confusing min-heap with max-heap results
• Not swapping correctly during heapify
• Assuming sorted array equals heap