Heap Extract Min or Max Bubble Down in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to get the left child index in a heap array.

DSA Javascript

function leftChildIndex(parentIndex) {
  return 2 * parentIndex [1] 1;
}

Drag options to blanks, or click blank then click option'

A+

B-

C/

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition

Using division or multiplication incorrectly

The left child index in a heap is calculated as 2 * parentIndex + 1.

2fill in blank

medium

Complete the code to swap two elements in the heap array.

DSA Javascript

function swap(heap, i, j) {
  const temp = heap[i];
  heap[i] = heap[[1]];
  heap[j] = temp;
}

Drag options to blanks, or click blank then click option'

Aheap

Bi

Cj

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with wrong indices

Using variable names incorrectly

To swap elements at indices i and j, assign heap[i] = heap[j].

3fill in blank

hard

Fix the error in the bubbleDown function to correctly compare and swap with the smaller child in a min-heap.

DSA Javascript

function bubbleDown(heap, index) {
  const left = 2 * index + 1;
  const right = 2 * index + 2;
  let smallest = index;

  if (left < heap.length && heap[left] [1] heap[smallest]) {
    smallest = left;
  }
  if (right < heap.length && heap[right] < heap[smallest]) {
    smallest = right;
  }
  if (smallest !== index) {
    swap(heap, index, smallest);
    bubbleDown(heap, smallest);
  }
}

Drag options to blanks, or click blank then click option'

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using greater than instead of less than

Using equality instead of comparison

In a min-heap, we swap if the child is smaller than the current smallest, so the comparison is <.

4fill in blank

hard

Fill both blanks to complete the extractMin function that removes the smallest element and restores the heap.

DSA Javascript

function extractMin(heap) {
  if (heap.length === 0) return null;
  const min = heap[0];
  heap[0] = heap[[1]];
  heap.[2]();
  bubbleDown(heap, 0);
  return min;
}

Drag options to blanks, or click blank then click option'

Aheap.length - 1

Bpop()

Cshift()

Dlength

Attempts:

3 left

💡 Hint

Common Mistakes

Using shift() which removes first element

Not removing last element after replacement

Replace root with last element (heap.length - 1) and remove last element with pop().

5fill in blank

hard

Fill all three blanks to complete the bubbleDown function for a max-heap that swaps with the larger child.

DSA Javascript

function bubbleDown(heap, index) {
  const left = 2 * index + 1;
  const right = 2 * index + 2;
  let largest = index;

  if (left < heap.length && heap[left] [1] heap[largest]) {
    largest = left;
  }
  if (right < heap.length && heap[right] [2] heap[largest]) {
    largest = right;
  }
  if (largest !== index) {
    swap(heap, index, largest);
    bubbleDown(heap, [3]);
  }
}

Drag options to blanks, or click blank then click option'

A>

B<

Clargest

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators

Recursing on wrong index

For max-heap, swap if child is greater (use > for comparison), and recurse on largest child index.

Practice

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

easy

A. To remove the largest element from the heap

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

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

D. To swap the last element with the root without any further changes

Solution

1. Step 1: Understand extract-min in a min-heap

   Extracting the minimum removes the root, which breaks the heap property.

2. Step 2: Role of bubble down

   Bubble down moves the new root element down to restore the min-heap property by swapping with smaller children.

3. Final Answer:

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

4. Quick Check:

   Bubble down fixes heap after extract-min [OK]

Hint: Bubble down fixes heap by pushing root down after extract [OK]

Common Mistakes:

• Thinking bubble down inserts new elements
• Confusing bubble down with bubble up
• Assuming bubble down removes largest element

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[j] in JavaScript during bubble down?

easy

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

B. swap(arr[i], arr[j]);

C. arr[i] = arr[j]; arr[j] = arr[i];

D. temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

Solution

1. Step 1: Identify JavaScript swap syntax

   ES6 allows swapping with destructuring: [a, b] = [b, a].

2. Step 2: Check each option

   [arr[i], arr[j]] = [arr[j], arr[i]]; uses correct destructuring syntax. temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; is valid but missing var or let for temp, so incomplete. Options A and C are incorrect syntax or logic.

3. Final Answer:

   [arr[i], arr[j]] = [arr[j], arr[i]]; -> Option A

4. Quick Check:

   Use destructuring swap in JS [OK]

Hint: Use ES6 destructuring for swap: [a,b]=[b,a] [OK]

Common Mistakes:

• Using undefined swap function
• Overwriting values without temp variable
• Incorrect assignment order causing same values

3. Given the min-heap array [2, 5, 3, 8, 10], after extracting the minimum and performing bubble down, what is the resulting heap array?

medium

A. [3, 5, 8, 10]

B. [5, 3, 8, 10]

C. [5, 8, 3, 10]

D. [3, 5, 10, 8]

Solution

1. Step 1: Extract min and replace root

   Remove 2 (root), move last element 10 to root: [10, 5, 3, 8]

2. Step 2: Bubble down 10

   Compare 10 with children 5 and 3. Smallest child is 3 at index 2. Swap 10 and 3: [3, 5, 10, 8]. Now 10 at index 2 has no children (indices 5 and 6 out of bounds), so stop.

3. Final Answer:

   [3, 5, 10, 8] -> Option D

4. Quick Check:

   Bubble down restores min-heap [OK]

Hint: Replace root with last, then swap down with smaller child [OK]

Common Mistakes:

• Not swapping with smallest child
• Forgetting to remove last element
• Swapping with larger child

4. Consider this bubble down code snippet for a max-heap extract operation:

function bubbleDown(arr, index) {
  let left = 2 * index + 1;
  let right = 2 * index + 2;
  let largest = index;
  if (left < arr.length && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < arr.length && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest !== index) {
    [arr[index], arr[largest]] = [arr[largest], arr[index]];
    bubbleDown(arr, largest);
  }
}

What is the bug if the heap array is empty after extract and bubbleDown is called with index 0?

medium

A. Infinite recursion because largest never equals index

B. No bug; function handles empty array correctly

C. Accessing arr[0] causes undefined behavior on empty array

D. Swapping elements without checking array length

Solution

1. Step 1: Analyze empty array case

   If arr is empty, arr.length = 0, left and right indices are 1 and 2, both >= length, so no swaps.

2. Step 2: Check access at arr[index]

   No accesses occur because child indices out of bounds and && short-circuits prevent evaluating arr[largest]. Function handles empty array safely.

3. Final Answer:

   No bug; function handles empty array correctly -> Option B

4. Quick Check:

   Check array length before accessing index [OK]

Hint: Always check array length before accessing indices [OK]

Common Mistakes:

• Assuming recursion stops automatically
• Ignoring empty array edge case
• Not validating index bounds

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

hard

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

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

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

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

Solution

1. Step 1: Extract max and replace root

   Remove 50 (root), move last element 35 to root: [35, 30, 40, 10, 20]

2. Step 2: Bubble down 35

   Compare 35 with children 30 and 40. Largest child is 40 at index 2. Swap 35 and 40: [40, 30, 35, 10, 20]. Now 35 at index 2 has children beyond array length, so stop.

3. Final Answer:

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

4. Quick Check:

   Bubble down swaps with largest child in max-heap [OK]

Hint: Swap root with largest child until heap property restored [OK]

Common Mistakes:

• Swapping with smaller child
• Not moving last element to root
• Stopping bubble down too early