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

Practice

1. What is the main purpose of the bubble down operation in a min-heap after extracting the minimum element?

easy

A. To delete the last element in the heap

B. To insert a new element at the bottom of the heap

C. To swap the minimum element with the maximum element

D. To restore the heap property by moving the root element down to its correct position

Solution

1. Step 1: Understand extract-min operation

   When the minimum element (root) is removed, the last element replaces the root.

2. Step 2: Apply bubble down to restore heap

   The bubble down moves this element down the tree to restore the min-heap property.

3. Final Answer:

   To restore the heap property by moving the root element down to its correct position -> Option D

4. Quick Check:

   Bubble down fixes heap after extract-min [OK]

Hint: Bubble down fixes heap after removing root [OK]

Common Mistakes:

• Confusing bubble down with insertion
• Thinking bubble down swaps min and max
• Assuming bubble down deletes elements

2. Which of the following TypeScript code snippets correctly swaps two elements in a heap array during bubble down?

easy

A. heap[i], heap[j] = heap[j], heap[i];

B. const temp = heap[i]; heap[i] = heap[j]; heap[j] = temp;

C. swap(heap[i], heap[j]);

D. heap[i] = heap[j]; heap[j] = heap[i];

Solution

1. Step 1: Check valid swap syntax in TypeScript

   const temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; uses a temporary variable to swap two elements correctly.

2. Step 2: Identify incorrect syntax in other options

   heap[i], heap[j] = heap[j], heap[i]; uses Python-style unpacking (invalid in TypeScript), C calls undefined function, D overwrites values incorrectly.

3. Final Answer:

   const temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; -> Option B

4. Quick Check:

   Use temp variable to swap in TypeScript [OK]

Hint: Use temp variable for swapping in TypeScript [OK]

Common Mistakes:

• Using Python tuple swap syntax in TypeScript
• Calling undefined swap function
• Overwriting values without temp variable

3. Consider the min-heap array [2, 5, 3, 10, 7]. After extracting the minimum element and performing bubble down, what is the resulting heap array?

medium

A. [3, 5, 7, 10]

B. [3, 7, 5, 10]

C. [5, 7, 3, 10]

D. [7, 5, 3, 10]

Solution

1. Step 1: Remove root and replace with last element

   Remove 2, replace root with 7: [7, 5, 3, 10]

2. Step 2: Bubble down 7 to restore min-heap

   Compare 7 with children 5 and 3; swap with smallest child 3: [3, 5, 7, 10]

3. Final Answer:

   [3, 5, 7, 10] -> Option A

4. Quick Check:

   Extract min and bubble down result = [3, 5, 7, 10] [OK]

Hint: Replace root with last, then bubble down [OK]

Common Mistakes:

• Not replacing root with last element
• Swapping with wrong child during bubble down
• Forgetting to remove last element

4. The following TypeScript code attempts to bubble down an element in a max-heap but does not work correctly. What is the main bug?

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

medium

A. Swapping elements overwrites values incorrectly without a temporary variable

B. The indices for left and right children are calculated incorrectly

C. The recursive call should be bubbleUp instead of bubbleDown

D. The condition to check children is reversed for max-heap

Solution

1. Step 1: Analyze swap logic in code

   The swap uses heap[i] = heap[largest]; heap[largest] = heap[i]; which overwrites heap[i] before assigning heap[largest].

2. Step 2: Identify correct swap method

   Swapping requires a temporary variable to avoid overwriting values.

3. Final Answer:

   Swapping elements overwrites values incorrectly without a temporary variable -> Option A

4. Quick Check:

   Swap needs temp variable to avoid overwrite [OK]

Hint: Always use temp variable when swapping array elements [OK]

Common Mistakes:

• Overwriting values during swap without temp
• Confusing bubbleDown with bubbleUp
• Incorrect child index calculations

5. You have a max-heap represented by the array [50, 30, 40, 10, 20, 35]. After extracting the maximum element and performing bubble down, what is the final heap array?

hard

A. [35, 30, 40, 10, 20]

B. [40, 30, 20, 10, 35]

C. [40, 30, 35, 10, 20]

D. [30, 20, 35, 10, 40]

Solution

1. Step 1: Remove max (root) and replace with last element

   Remove 50, replace root with 35: [35, 30, 40, 10, 20]

2. Step 2: Bubble down 35 to restore max-heap

   Compare 35 with children 30 and 40; swap with largest child 40: [40, 30, 35, 10, 20]

3. Final Answer:

   [40, 30, 35, 10, 20] -> Option C

4. Quick Check:

   Extract max and bubble down result = [40, 30, 35, 10, 20] [OK]

Hint: Replace root with last, then bubble down largest child [OK]

Common Mistakes:

• Swapping with wrong child during bubble down
• Not removing last element after replacement
• Confusing min-heap bubble down with max-heap