Build Heap from Array Heapify in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to get the index of the last non-leaf node in the heap array.

DSA Typescript

const lastNonLeaf = Math.floor((arr.length - 2) / [1]);

Drag options to blanks, or click blank then click option'

A2

B3

C1

D4

Attempts:

3 left

💡 Hint

Common Mistakes

Using length / 2 instead of (length - 2) / 2

Using 3 instead of 2 as divisor

Confusing leaf nodes with non-leaf nodes

In a binary heap stored as an array, the last non-leaf node is at index floor((n-2)/2).

2fill in blank

medium

Complete the code to swap two elements in the array during heapify.

DSA Typescript

const temp = arr[i]; arr[i] = arr[[1]]; arr[[1]] = temp;

Drag options to blanks, or click blank then click option'

Aparent

Bsmallest

Clargest

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with 'smallest' instead of 'largest'

Swapping with 'parent' which is the current node itself

Using an undefined variable

During heapify, we swap the current node with the largest child to maintain the heap property.

3fill in blank

hard

Fix the error in the heapify function's recursive call to maintain heap property.

DSA Typescript

if (largest !== i) { heapify(arr, arr.length, [1]); }

Drag options to blanks, or click blank then click option'

Alargest

Bi

C0

Darr.length

Attempts:

3 left

💡 Hint

Common Mistakes

Calling heapify with 'i' which causes infinite recursion

Calling heapify with 0 which restarts from root unnecessarily

Using arr.length as index which is out of bounds

After swapping, heapify must be called recursively on the index 'largest' to fix the subtree.

4fill in blank

hard

Fill both blanks to complete the loop that builds the heap from the array.

DSA Typescript

for (let i = [1]; i >= 0; i[2]) { heapify(arr, arr.length, i); }

Drag options to blanks, or click blank then click option'

AMath.floor(arr.length / 2) - 1

B0

C--

D++

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from 0 and incrementing instead of decrementing

Using ++ instead of -- in the loop

Starting from arr.length instead of last non-leaf node

The build heap process starts from the last non-leaf node down to the root, decrementing i each time.

5fill in blank

hard

Fill all three blanks to complete the heapify function header and left child calculation.

DSA Typescript

function heapify(arr: number[], n: number, [1]: number) {
  const left = 2 * [2] + [3];
  // rest of heapify code
}

Drag options to blanks, or click blank then click option'

Ai

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of 1 for left child offset

Using different variable names inconsistently

Confusing left child with right child index

The heapify function uses 'i' as the current index, and left child is at 2*i + 1 in a binary 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