Build Heap from Array Heapify in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output array after building a max heap?

Given the array [3, 9, 2, 1, 4, 5], what is the array representation after applying the build max heap process?

DSA Typescript

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

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

const input = [3, 9, 2, 1, 4, 5];
console.log(buildMaxHeap(input));

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

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

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

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

💡 Hint

Start heapifying from the last non-leaf node and move upwards.

The build max heap process starts heapifying from the last non-leaf node (index 2) up to the root (index 0). After heapifying, the array becomes [9, 4, 5, 1, 3, 2].

❓ Predict Output

intermediate

What is the output after building a min heap?

Given the array [7, 2, 6, 3, 9, 1], what is the array representation after applying the build min heap process?

DSA Typescript

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

function minHeapify(arr: number[], n: number, i: number): void {
  let smallest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[left] < arr[smallest]) {
    smallest = left;
  }

  if (right < n && arr[right] < arr[smallest]) {
    smallest = right;
  }

  if (smallest !== i) {
    [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
    minHeapify(arr, n, smallest);
  }
}

const input = [7, 2, 6, 3, 9, 1];
console.log(buildMinHeap(input));

A [1, 2, 7, 3, 9, 6]

B [2, 3, 1, 7, 9, 6]

C [1, 2, 6, 3, 9, 7]

D [1, 3, 2, 7, 9, 6]

💡 Hint

Heapify from the last non-leaf node upwards to maintain min heap property.

Starting from index 2, heapify ensures the smallest element is at the root. The final min heap array is [1, 2, 7, 3, 9, 6].

🔧 Debug

advanced

Identify the error in this heapify implementation

What error will this code produce when building a max heap from array [4, 10, 3, 5, 1]?

DSA Typescript

function heapify(arr: number[], n: number, i: number): void {
  let largest = i;
  const left = 2 * i + 1;
  const 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 buildMaxHeap(arr: number[]): number[] {
  const n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
  return arr;
}

const input = [4, 10, 3, 5, 1];
console.log(buildMaxHeap(input));

A No error, outputs [10, 5, 3, 4, 1]

B TypeError: Cannot read property '5' of undefined

C IndexError: list index out of range

D SyntaxError: Unexpected token

💡 Hint

Check the boundary conditions for left and right child indices.

The condition uses 'left <= n' and 'right <= n' which allows index equal to n, causing out-of-bound access. It should be 'left < n' and 'right < n'.

🧠 Conceptual

advanced

Why does build heap run in O(n) time, not O(n log n)?

Which explanation best describes why the build heap operation using heapify runs in linear time O(n) instead of O(n log n)?

A Because the number of nodes at each level decreases exponentially while heapify cost increases linearly, balancing to O(n).

B Because heapify is called only on leaf nodes which take constant time each.

C Because the array is already sorted before building the heap.

D Because heapify uses a divide and conquer approach that halves the problem size each time.

💡 Hint

Consider how many nodes are at each level and how much work heapify does per node.

Heapify cost per node depends on height. There are fewer nodes at higher levels with more cost, and many nodes at lower levels with less cost. Summing all gives O(n).

🚀 Application

expert

After building max heap, what is the heap array after extracting max once?

Given the array [4, 10, 3, 5, 1], after building a max heap and then extracting the max element once (removing root and heapifying), what is the resulting array?

DSA Typescript

function heapify(arr: number[], n: number, i: number): void {
  let largest = i;
  const left = 2 * i + 1;
  const 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 buildMaxHeap(arr: number[]): void {
  const n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
}

function extractMax(arr: number[]): number | null {
  const n = arr.length;
  if (n === 0) return null;
  const max = arr[0];
  arr[0] = arr[n - 1];
  arr.pop();
  heapify(arr, arr.length, 0);
  return max;
}

const input = [4, 10, 3, 5, 1];
buildMaxHeap(input);
extractMax(input);
console.log(input);

A [10, 5, 3, 1]

B [5, 1, 3, 4]

C [4, 5, 3, 1]

D [5, 4, 3, 1]

💡 Hint

After removing max, replace root with last element and heapify down.

After building max heap, the array is [10, 5, 3, 4, 1]. Extracting max removes 10, replaces root with 1, then heapifies to [5, 4, 3, 1].

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