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

Practice - 5 Tasks

1fill in blank

easy

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

DSA Typescript

function leftChildIndex(parentIndex: number): number {
  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 multiplication or division incorrectly.

In a heap stored as an array, the left child of a node at index i is at 2 * i + 1.

2fill in blank

medium

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

DSA Typescript

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

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

Aj

Bi

C0

Dheap.length - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with the wrong index.

Using the same index for both assignments.

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

3fill in blank

hard

Fix the error in the bubbleDown function to correctly update the index after swapping.

DSA Typescript

function bubbleDown(heap: number[], index: number): void {
  const length = heap.length;
  let smallest = index;
  const left = 2 * index + 1;
  const right = 2 * index + 2;

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

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

Aleft

Bindex

Csmallest

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Not updating the index at all.

Updating index to the old value instead of the child's index.

After swapping, the new index to continue bubbling down is the smallest child index.

4fill in blank

hard

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

DSA Typescript

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

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

Aheap.length - 1

B0

C1

Dheap.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices for replacement or bubble down.

Not popping the last element before bubbling down.

Replace the root with the last element at index heap.length - 1, then bubble down from index 0.

5fill in blank

hard

Fill all three blanks to complete the bubbleDown function for a max heap.

DSA Typescript

function bubbleDownMax(heap: number[], index: number): void {
  const length = heap.length;
  let largest = index;
  const left = 2 * index + 1;
  const right = 2 * index + 2;

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

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

A>

B<

Clargest

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' for max heap comparisons.

Not updating index correctly after swap.

For a max heap, compare if children are greater than current largest, then update largest and continue bubbling down from largest.

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