Heap Extract Min or Max Bubble Down in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after extracting min from this min-heap?

Given the min-heap array representation [2, 5, 3, 9, 6], what is the heap array after extracting the minimum element and performing bubble down?

DSA Typescript

function extractMin(heap: number[]): number[] {
  const min = heap[0];
  heap[0] = heap[heap.length - 1];
  heap.pop();
  let i = 0;
  while (true) {
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let smallest = i;
    if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
    if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
    if (smallest === i) break;
    [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
    i = smallest;
  }
  return heap;
}

console.log(extractMin([2, 5, 3, 9, 6]));

A [3, 5, 6, 9]

B [3, 6, 5, 9]

C [5, 3, 6, 9]

D [5, 6, 3, 9]

💡 Hint

Remember to replace the root with the last element and bubble down by swapping with the smaller child.

After removing 2, replace root with 6. Then bubble down: 6 swaps with 3 (smaller child), resulting in [3, 5, 6, 9].

❓ Predict Output

intermediate

What is the heap after extracting max from this max-heap?

Given the max-heap array [20, 15, 18, 8, 10, 17], what is the array after extracting the maximum element and bubble down?

DSA Typescript

function extractMax(heap: number[]): number[] {
  const max = heap[0];
  heap[0] = heap[heap.length - 1];
  heap.pop();
  let i = 0;
  while (true) {
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let largest = i;
    if (left < heap.length && heap[left] > heap[largest]) largest = left;
    if (right < heap.length && heap[right] > heap[largest]) largest = right;
    if (largest === i) break;
    [heap[i], heap[largest]] = [heap[largest], heap[i]];
    i = largest;
  }
  return heap;
}

console.log(extractMax([20, 15, 18, 8, 10, 17]));

A [17, 15, 18, 8, 10]

B [18, 15, 17, 8, 10]

C [15, 18, 17, 8, 10]

D [18, 15, 10, 8, 17]

💡 Hint

Replace root with last element and bubble down by swapping with the larger child.

After removing 20, replace root with 17. Bubble down swaps 17 with 18 (larger child), resulting in [18, 15, 17, 8, 10].

🔧 Debug

advanced

Identify the bug in this bubble down implementation for min-heap extract

This code is supposed to extract the minimum from a min-heap and bubble down the root. What is the bug causing incorrect heap after extraction?

DSA Typescript

function extractMinBuggy(heap: number[]): number[] {
  const min = heap[0];
  heap[0] = heap.pop()!;
  let i = 0;
  while (true) {
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let smallest = i;
    if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
    if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
    if (smallest === i) break;
    [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
    i = smallest;
  }
  return heap;
}

console.log(extractMinBuggy([2, 5, 3, 9, 6]));

A Using heap.pop()! to replace root removes last element but does not handle empty heap correctly.

B Using heap.pop()! directly assigns undefined when heap is empty, causing errors.

C Assigning heap[0] = heap.pop()! removes last element but does not reduce heap size properly.

D Replacing root with heap.pop()! before popping removes the last element twice.

💡 Hint

Check what happens when heap.pop() returns undefined and how root is replaced.

Using heap.pop()! replaces root with last element but if heap is empty after pop, root becomes undefined causing errors. Proper check or separate pop then assign is safer.

🧠 Conceptual

advanced

Why does bubble down maintain heap property after extraction?

After extracting the root from a heap and replacing it with the last element, why does the bubble down process restore the heap property?

A Because bubble down inserts a new element at the root and shifts others down.

B Because bubble down sorts the entire heap array to maintain order.

C Because bubble down removes all leaf nodes that violate the heap property.

D Because bubble down swaps the root with the smallest/largest child until the heap property is restored at every level.

💡 Hint

Think about how heap property depends on parent-child relationships.

Bubble down compares the root with its children and swaps with the smaller (min-heap) or larger (max-heap) child to fix violations, repeating until heap property holds.

❓ Predict Output

expert

What is the heap array after extracting min twice from this min-heap?

Given the min-heap array [1, 3, 6, 5, 9, 8], what is the heap array after extracting the minimum element twice (with bubble down after each extraction)?

DSA Typescript

function extractMin(heap: number[]): number[] {
  const min = heap[0];
  heap[0] = heap[heap.length - 1];
  heap.pop();
  let i = 0;
  while (true) {
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let smallest = i;
    if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
    if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
    if (smallest === i) break;
    [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
    i = smallest;
  }
  return heap;
}

let heap = [1, 3, 6, 5, 9, 8];
heap = extractMin(heap);
heap = extractMin(heap);
console.log(heap);

A [3, 6, 8, 9]

B [6, 5, 8, 9]

C [5, 8, 6, 9]

D [3, 5, 6, 9]

💡 Hint

Perform extraction and bubble down step by step twice.

First extraction removes 1, replaces root with 8 → [8, 3, 6, 5, 9], bubble down: swaps 8 with 3 → [3, 8, 6, 5, 9], then 8 with 5 → [3, 5, 6, 8, 9]. Second extraction removes 3, replaces root with 9 → [9, 5, 6, 8], bubble down: swaps 9 with 5 → [5, 9, 6, 8], then 9 with 8 → [5, 8, 6, 9].