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.

Practice

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

easy

A. To reverse the array elements

B. To sort the array in ascending order

C. To find the maximum element in the array

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 each parent node is greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role of heapify

   Heapify rearranges elements so the heap property holds for every subtree, starting from a node downwards.

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 subtree to maintain heap order [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 way to start heapifying an array arr of length n in JavaScript to build a max heap?

easy

A. for(let i = 0; i < n; i++) heapify(arr, i, n);

B. for(let i = 1; i < n; i++) heapify(arr, i, n);

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

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

Solution

1. Step 1: Identify heapify start index

   Heapify starts from the last non-leaf node, which is at index Math.floor(n/2) - 1.

2. Step 2: Loop backwards to root

   We heapify each node from this index down to 0 to ensure the entire tree satisfies heap property.

3. Final Answer:

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

4. Quick Check:

   Start heapify at last non-leaf node [OK]

Hint: Start heapify from last parent node backwards [OK]

Common Mistakes:

• Starting heapify from index 0 forwards
• Heapifying leaf nodes unnecessarily
• Using incorrect loop boundaries

3. Given the array [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. [9, 4, 5, 3, 1, 2]

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

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

Solution

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

   Heapify at index 2: children are indices 5 (5) and no right child. 2 < 5, swap to get [3,9,5,1,4,2].

2. Step 2: Heapify at index 1

   Children at indices 3 (1) and 4 (4). 9 > 4 and 1, no swap needed.

3. Step 3: Heapify at index 0

   Children at indices 1 (9) and 2 (5). 3 < 9, swap 3 and 9: [9,3,5,1,4,2]. Heapify at index 1 again: children 3 (1) and 4 (4). 3 < 4, swap: [9,4,5,1,3,2].

4. Final Answer:

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

5. Quick Check:

   Max heap root is 9, children smaller [OK]

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

Common Mistakes:

• Not heapifying children after swap
• Swapping with wrong child
• Stopping heapify too early

4. Consider this heapify function snippet in JavaScript:

function heapify(arr, i, n) {
  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, largest, n);
  }
}

What is the bug if the function is called with heapify(arr, 0, arr.length - 1) instead of heapify(arr, 0, arr.length)?

medium

A. It will ignore the last element of the array during heapify

B. It will cause an infinite recursion

C. It will throw a syntax error

D. It will heapify the entire array correctly

Solution

1. Step 1: Understand parameter n meaning

   Parameter n is the array length limit for heapify to avoid out-of-bound access.

2. Step 2: Effect of passing arr.length - 1

   Passing arr.length - 1 excludes the last element index (n-1) from heapify checks, so last element is ignored.

3. Final Answer:

   It will ignore the last element of the array during heapify -> Option A

4. Quick Check:

   n must be array length, not length-1 [OK]

Hint: Use full array length as heapify limit [OK]

Common Mistakes:

• Confusing length and last index
• Expecting syntax error instead of logic error
• Ignoring off-by-one errors

5. You have an array [4, 10, 3, 5, 1] and want to build a min heap using heapify. Which of the following changes is necessary in the heapify function to build a min heap instead of a max heap?

hard

A. Swap the left and right child indices calculations

B. Change comparisons from '>' to '<' when comparing children with parent

C. Change comparisons from '<' to '>' when comparing children with parent

D. No change needed; heapify works for both min and max heaps

Solution

1. Step 1: Understand max vs min heap comparison

   Max heap keeps parent >= children; min heap keeps parent <= children.

2. Step 2: Adjust comparison operators

   To build min heap, change '>' to '<' so parent is smaller than children.

3. Final Answer:

   Change comparisons from '>' to '<' when comparing children with parent -> Option B

4. Quick Check:

   Min heap uses less-than comparisons [OK]

Hint: Flip comparison signs for min heap [OK]

Common Mistakes:

• Swapping child indices instead of comparisons
• Leaving comparisons unchanged
• Assuming heapify auto-detects heap type