Heap Extract Min or Max Bubble Down in DSA Javascript - 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, what is the heap array after extracting the minimum element and performing bubble down?

DSA Javascript

const heap = [2, 5, 3, 9, 7];

function extractMin(heap) {
  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(extractMin(heap));

A [3, 5, 7, 9]

B [3, 7, 5, 9]

C [5, 3, 7, 9]

D [5, 7, 3, 9]

💡 Hint

Remember after removing the root, replace it with the last element and bubble down to restore heap property.

After removing 2, replace root with 7. Bubble down swaps 7 with 3 (left child). Final heap is [3, 5, 7, 9].

❓ Predict Output

intermediate

What is the max-heap array after extracting max and bubbling down?

Given this max-heap array, what is the array after extracting the maximum element and performing bubble down?

DSA Javascript

const heap = [20, 15, 18, 8, 10, 17];

function extractMax(heap) {
  const max = heap[0];
  heap[0] = 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(heap));

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

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

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

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

💡 Hint

After removing the root, replace it with the last element and bubble down to maintain max-heap.

After removing 20, replace root with 17. Bubble down swaps 17 with 18 (right child). Final heap is [18, 15, 17, 8, 10].

🔧 Debug

advanced

Why does this bubble down function fail to restore min-heap?

This bubble down function is supposed to restore min-heap after extraction but fails on some inputs. What is the bug?

DSA Javascript

function bubbleDown(heap, i) {
  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) {
    [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
    bubbleDown(heap, smallest);
  }
}

const heap = [1, 3, 6, 5, 9, 8];
heap[0] = heap[heap.length - 1];
bubbleDown(heap, 0);
console.log(heap);

A The function does not return the heap after bubbling down, so changes are lost.

B The function uses recursion but does not update indices correctly, causing infinite recursion.

C The function does not check if heap is empty before popping, causing errors.

D The function does not update the heap length after popping, causing out-of-bounds access.

💡 Hint

Check how the heap length changes after popping and how it affects index checks.

After popping, heap length decreases but bubbleDown uses old length causing index checks to fail and possible out-of-bounds access.

🧠 Conceptual

advanced

What is the time complexity of bubble down operation in a heap?

Consider a heap with n elements. What is the time complexity of the bubble down operation after extracting the root?

A O(log n) because bubble down moves down one level at a time in the heap tree.

B O(n) because bubble down may need to check all elements in the heap array.

C O(1) because bubble down only swaps the root with one child once.

D O(n log n) because bubble down involves sorting the heap after extraction.

💡 Hint

Think about the height of a binary heap and how many swaps bubble down can perform.

Bubble down moves down the height of the heap, which is log n for n elements, so time complexity is O(log n).

🚀 Application

expert

After multiple extractMin operations, what is the heap array?

Starting with this min-heap array, perform extractMin twice (removing min and bubbling down each time). What is the resulting heap array?

DSA Javascript

let heap = [1, 3, 6, 5, 9, 8, 15];

function extractMin(heap) {
  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;
}

extractMin(heap);
extractMin(heap);
console.log(heap);

A [3, 5, 6, 8, 9]

B [5, 8, 6, 15, 9]

C [6, 8, 15, 9]

D [5, 8, 15, 9, 6]

💡 Hint

Perform extractMin step-by-step, updating the heap array and bubbling down each time.

First extractMin removes 1, replaces root with 15, bubble down swaps 15 with 3 then 5. Heap becomes [3, 5, 6, 15, 9, 8]. Second extractMin removes 3, replaces root with 8, bubble down swaps 8 with 5. Final heap is [5, 8, 6, 15, 9].