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

Concept Flow - Heap Extract Min or Max Bubble Down

Start: Extract root (min or max)

↓

Replace root with last element

↓

Remove last element from heap

↓

Set current index = 0

↓

Compare current with children

↓

Left child

↓

Find smaller/larger child

↓

If current violates heap property

↓

Swap current with child

↓

Update current index to child's index

↓

Repeat comparison until heap property restored

↓

Done

This flow shows how extracting the root from a heap replaces it with the last element, then moves that element down by swapping with children until the heap property is restored.

Execution Sample

DSA C++

heap = [10, 15, 30, 40, 50, 100, 40]
extract_min():
  root = heap[0]
  heap[0] = heap.pop()
  bubble_down(0)

Extract the minimum element from a min-heap and restore heap property by bubbling down.

Execution Table

Step	Operation	Heap Array	Current Index	Left Child Index	Right Child Index	Swap?	Heap State Visual
1	Extract root (10)	[10, 15, 30, 40, 50, 100, 40]	0	1	2	No	Tree: 10 / \ 15 30 / \ / \ 40 50 100 40
2	Replace root with last element (40)	[40, 15, 30, 40, 50, 100]	0	1	2	No	Tree: 40 / \ 15 30 / \ / 40 50 100
3	Compare current (40) with children (15, 30)	Same	0	1	2	Yes (swap with 15)	Before swap: 40 / \ 15 30 / \ / 40 50 100
4	Swap current with left child	[15, 40, 30, 40, 50, 100]	1	3	4	No	After swap: 15 / \ 40 30 / \ / 40 50 100
5	Compare current (40) with children (40, 50)	Same	1	3	4	No	Current node 40 has children 40 and 50, no swap needed
6	Bubble down complete	[15, 40, 30, 40, 50, 100]	N/A	N/A	N/A	No	Final heap: 15 / \ 40 30 / \ / 40 50 100

💡 Heap property restored; no further swaps needed.

Variable Tracker

Variable	Start	After Step 2	After Step 4	Final
heap	[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]
current_index	0	0	1	1
left_child_index	1	1	3	3
right_child_index	2	2	4	4
swap_occurred	No	No	Yes	No

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 2 where root 10 is replaced by last element 40.

Why do we compare the current node with both children before swapping?

We must find the smaller child (for min-heap) to swap with to maintain heap property. See step 3 where current 40 is compared with children 15 and 30, and swap happens with smaller child 15.

When does bubbling down stop?

Bubbling down stops when the current node is smaller than both children (min-heap) or no children exist. See step 5 where current 40 has children 40 and 50 but no swap is needed, so bubbling down ends.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, which child does the current node swap with?

A Left child (15)

B Right child (30)

C No swap occurs

D Both children simultaneously

💡 Hint

Refer to 'Swap?' and 'Heap State Visual' columns in step 3 of execution_table.

At which step does the heap property get fully restored?

A Step 2

B Step 4

C Step 5

D Step 6

💡 Hint

Check the 'Operation' and 'Heap State Visual' columns; step 6 shows 'Bubble down complete'.

If the last element was smaller than both children, what would happen in the bubble down?

A No swaps; bubble down ends immediately

B Swap with left child only

C Swap with right child only

D Swap with both children

💡 Hint

See step 5 where no swap occurs because current node is smaller than children.

Concept Snapshot

Heap Extract Min/Max Bubble Down:
- Remove root (min or max element).
- Replace root with last element.
- Remove last element from heap.
- Bubble down: swap with smaller/larger child to restore heap.
- Stop when heap property is restored or no children.

Full Transcript

Heap extract min or max operation removes the root element from the heap. To keep the heap complete, the last element replaces the root. Then, the bubble down process compares this element with its children and swaps it with the smaller (min-heap) or larger (max-heap) child if heap property is violated. This repeats until the heap property is restored or no children remain. The execution table shows each step with heap array state, current index, children indices, and swaps. Variable tracker follows heap array and indices. Key moments clarify why replacement and comparisons happen. Visual quiz tests understanding of swap decisions and termination.

Practice

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

easy

A. To restore the min-heap property by moving the root element down to its correct position

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

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

D. To remove the maximum element from the heap

Solution

1. Step 1: Understand extract-min operation

   When the minimum element (root) is removed, the last element is moved to the root position.

2. Step 2: Apply bubble down to restore heap

   The bubble down operation moves this element down the tree to restore the min-heap property by swapping with the smaller child.

3. Final Answer:

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

4. Quick Check:

   Bubble down fixes heap after extract-min [OK]

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

Common Mistakes:

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

2. Which of the following is the correct C++ syntax to swap two elements heap[i] and heap[j] during bubble down?

easy

A. swap(heap[i], heap[j]){}

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

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

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

Solution

1. Step 1: Recall C++ swap function usage

   The standard way to swap two variables in C++ is using swap(a, b); from <algorithm>.

2. Step 2: Check each option

   swap(heap[i], heap[j]); uses correct syntax. heap[i] = heap[j]; heap[j] = heap[i]; wrongly assigns values without temporary storage. Options C and D have invalid syntax.

3. Final Answer:

   swap(heap[i], heap[j]); -> Option D

4. Quick Check:

   Correct swap syntax = swap(heap[i], heap[j]); [OK]

Hint: Use standard swap function with two variables [OK]

Common Mistakes:

• Assigning without temporary variable causes errors
• Adding extra symbols after swap call
• Using braces {} after swap incorrectly

3. Given 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. [5, 3, 7, 10]

Solution

1. Step 1: Remove minimum and replace root

   Remove 2 (root). Move last element 7 to root: [7, 5, 3, 10]

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

   Compare 7 with children 5 and 3. Smallest child is 3. Swap 7 and 3: [3, 5, 7, 10]. Now 7 has children 10 only, no swap needed.

3. Final Answer:

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

4. Quick Check:

   Bubble down swaps root with smallest child [OK]

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

Common Mistakes:

• Not swapping with smallest child first
• Forgetting to replace root with last element
• Swapping with larger child by mistake

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

void bubbleDown(vector<int>& heap, int i) {
  int left = 2*i + 1;
  int right = 2*i + 2;
  int largest = i;
  if (left < heap.size() && heap[left] > heap[largest])
    largest = left;
  if (right < heap.size() && heap[right] > heap[largest])
    largest = right;
  if (largest != i) {
    swap(heap[i], heap[largest]);
    bubbleDown(heap, largest);
  }
}

What is the bug if the heap size is 1 and bubbleDown(heap, 0) is called?

medium

A. Infinite recursion because largest never changes

B. No bug; function handles size 1 correctly

C. Accessing left child index 1 causes out-of-range error

D. Swap called even when largest equals i

Solution

1. Step 1: Check conditions for size 1 heap

   For size 1, left = 1 and right = 2, both >= heap.size(), so conditions fail and largest stays i.

2. Step 2: Confirm no recursion or swap

   Since largest == i, no swap or recursive call happens. Function returns safely.

3. Final Answer:

   No bug; function handles size 1 correctly -> Option B

4. Quick Check:

   Bounds checked before access prevents errors [OK]

Hint: Check index bounds before accessing children [OK]

Common Mistakes:

• Assuming out-of-range access without checking
• Thinking recursion always happens
• Swapping when largest equals current index

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

hard

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

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

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

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

Solution

1. Step 1: Remove max and replace root

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

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

   Compare 35 with children 30 and 40. Largest child is 40. Swap 35 and 40: [40, 30, 35, 10, 20]. Now 35 has children 10 and 20, both smaller, so stop.

3. Final Answer:

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

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 instead of largest
• Not replacing root with last element before bubble down
• Stopping bubble down too early