Heap Extract Min or Max Bubble Down in DSA Javascript - Execution Trace

Concept Flow - Heap Extract Min or Max Bubble Down

Start with heap array

↓

Remove root element

↓

Replace root with last element

↓

Bubble down: Compare with children

↓

Swap with smaller (min-heap) or larger (max-heap) child if needed

↓

Repeat bubble down until heap property restored

↓

Return extracted root

This flow shows how the root element is removed and the last element is moved down the heap to restore order.

Execution Sample

DSA Javascript

function extractRoot(heap) {
  const root = heap[0];
  const end = heap.pop();
  if (heap.length > 0) {
    heap[0] = end;
    bubbleDown(heap, 0);
  }
  return root;
}

This code removes the root of the heap, replaces it with the last element, then bubbles it down to restore heap order.

Execution Table

Step	Operation	Heap Array	Pointer Changes	Visual State
1	Initial heap	[10, 15, 30, 40, 50, 100, 40]	root → index 0 (10)	10 / \ 15 30 / \ / \ 40 50 100 40
2	Remove root (10)	[10, 15, 30, 40, 50, 100, 40]	root extracted	Root 10 extracted
3	Replace root with last element (40)	[40, 15, 30, 40, 50, 100]	root → index 0 now 40 (was last)	40 / \ 15 30 / \ / 40 50 100
4	Bubble down from index 0 (40)	[40, 15, 30, 40, 50, 100]	Compare 40 with children 15 (index 1) and 30 (index 2)	Current:40, Left child:15, Right child:30
5	Swap with smaller child (15)	[15, 40, 30, 40, 50, 100]	Swap index 0 and 1	15 / \ 40 30 / \ / 40 50 100
6	Continue bubble down at index 1 (40)	[15, 40, 30, 40, 50, 100]	Compare 40 with children 40 (index 3) and 50 (index 4)	Current:40, Left child:40, Right child:50
7	No swap needed (40 ≤ 40 and 50)	[15, 40, 30, 40, 50, 100]	Bubble down ends	15 / \ 40 30 / \ / 40 50 100
8	Return extracted root	[15, 40, 30, 40, 50, 100]	Returned 10	15 / \ 40 30 / \ / 40 50 100

💡 Bubble down stops when current node is smaller than both children or no children exist

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
heap array	[10, 15, 30, 40, 50, 100, 40]	[40, 15, 30, 40, 50, 100]	[15, 40, 30, 40, 50, 100]	[15, 40, 30, 40, 50, 100]	[15, 40, 30, 40, 50, 100]
root extracted	N/A	10	10	10	10
current index	0	0	1	1	N/A
left child index	1	1	3	3	N/A
right child index	2	2	4	4	N/A

Key Moments - 3 Insights

Why do we replace the root with the last element before bubbling down?

Replacing the root with the last element keeps the heap complete (no gaps). Then bubbling down restores the heap order. See execution_table step 3 where last element 40 moves to root.

Why do we compare the current node with both children during bubble down?

To maintain heap property, the current node must be smaller (min-heap) than both children. We swap with the smaller child if needed. See execution_table steps 4 and 5 for comparisons and swap.

When does the bubble down process stop?

Bubble down stops when the current node is smaller than both children or has no children. See execution_table step 7 where no swap is needed and bubble down ends.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, which elements are swapped?

A Elements at index 0 and 1 (40 and 15)

B Elements at index 1 and 3 (40 and 40)

C Elements at index 0 and 2 (40 and 30)

D No elements are swapped

💡 Hint

Check the 'Swap with smaller child' operation and the heap array before and after step 5

At which step does the bubble down process stop?

A Step 4

B Step 6

C Step 7

D Step 8

💡 Hint

Look for the step where 'No swap needed' and 'Bubble down ends' are mentioned

If the last element was larger than the root, what would happen at step 3?

A The root would be replaced but no bubble down needed

B The root would be replaced and bubble down would swap it down

C The root would not be replaced

D The heap would become incomplete

💡 Hint

Refer to the bubble down logic in execution_table steps 3 to 7

Concept Snapshot

Heap Extract Min or Max Bubble Down:
- Remove root element (min or max)
- Replace root with last element
- Bubble down: swap with smaller (min) or larger (max) child
- Repeat until heap property restored
- Return extracted root

Full Transcript

This visualization shows how to remove the root element from a heap and restore heap order by bubbling down the last element moved to the root. The process starts by removing the root and replacing it with the last element in the heap array. Then, the bubble down operation compares this element with its children and swaps it with the smaller child in a min-heap if needed. This repeats until the element is smaller than both children or has no children. The final heap maintains the heap property and the extracted root is returned.

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