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].