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

↓

Child smaller/larger?

↓

Swap current with child

↓

Update current index to child

↩Back to Compare current with children

This flow shows how extracting the root from a heap replaces it with the last element, then 'bubbles down' this element by swapping it with the smaller (min-heap) or larger (max-heap) child until heap property is restored.

Execution Sample

DSA C#

int ExtractMin(int[] heap, ref int size) {
  int min = heap[0];
  heap[0] = heap[size - 1];
  size--;
  BubbleDown(heap, 0, size);
  return min;
}

Extracts the minimum element from a min-heap, replaces root with last element, reduces size, then bubbles down to restore heap.

Execution Table

Step	Operation	Heap Array	Current Index	Swap Action	Heap Visual State
1	Extract root (min=10)	[10, 15, 30, 40, 50, 100, 40]	0	None	Tree: 10 / \ 15 30 / \ / \ 40 50 100 40
2	Replace root with last element (40)	[40, 15, 30, 40, 50, 100, 40]	0	None	Tree: 40 / \ 15 30 / \ / \ 40 50 100 40
3	Remove last element (size=6)	[40, 15, 30, 40, 50, 100]	0	None	Tree: 40 / \ 15 30 / \ / 40 50 100
4	Compare current(40) with children 15 and 30	[40, 15, 30, 40, 50, 100]	0	Swap with 15 (index 1)	Tree: 40 / \ 15 30 / \ / 40 50 100
5	Swap current(40) with child(15)	[15, 40, 30, 40, 50, 100]	1	Swap	Tree: 15 / \ 40 30 / \ / 40 50 100
6	Compare current(40 at index 1) with children 40 and 50	[15, 40, 30, 40, 50, 100]	1	No swap needed	Tree: 15 / \ 40 30 / \ / 40 50 100
7	Bubble down complete	[15, 40, 30, 40, 50, 100]	1	None	Tree: 15 / \ 40 30 / \ / 40 50 100

💡 No swap needed at step 6, heap property restored, bubble down ends.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	Final
heap	[10, 15, 30, 40, 50, 100, 40]	[40, 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]
size	7	7	6	6	6	6
currentIndex	0	0	0	1	1	1
swapPerformed	No	No	No	Yes	No	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 and 3 where root is replaced and last element removed.

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

We must find the smaller (min-heap) or larger (max-heap) child to swap with to maintain heap order. In step 4, current 40 is compared with children 15 and 30 to decide swap.

When does the bubble down stop?

Bubble down stops when current node is smaller (min-heap) or larger (max-heap) than both children, so no swap is needed. This happens at step 6 in the execution_table.

Visual Quiz - 3 Questions

Look at the execution table, what is the heap array after step 5?

A [15, 40, 30, 40, 50, 100]

B [40, 15, 30, 40, 50, 100]

C [10, 15, 30, 40, 50, 100]

D [15, 30, 40, 40, 50, 100]

💡 Hint

Check the 'Heap Array' column at step 5 in the execution_table.

At which step does the bubble down process stop?

A Step 4

B Step 6

C Step 3

D Step 7

💡 Hint

Look for 'No swap needed' and 'Bubble down complete' in the execution_table.

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

A Swap with the smaller child

B No swap, bubble down ends

C Swap with the larger child

D Remove last element without replacement

💡 Hint

Bubble down swaps with smaller child to restore heap order, see step 4 swap action.

Concept Snapshot

Heap Extract Min/Max Bubble Down:
- Remove root (min or max element)
- Replace root with last element
- Reduce heap size
- Bubble down: swap with smaller (min) or larger (max) child
- Stop when heap property restored
- Maintains complete binary tree and heap order

Full Transcript

This concept shows how to remove the root element from a heap and restore the heap property by bubbling down the replacement element. First, the root is extracted and replaced by the last element in the heap array. Then the last element is removed, reducing the heap size. Starting at the root index, the element is compared with its children. If it violates the heap order, it swaps with the smaller child in a min-heap or larger child in a max-heap. This process repeats until no swaps are needed, restoring the heap property. The execution table traces each step with the heap array and visual tree state. Key moments clarify why replacement and comparisons happen, and when bubbling down stops. The visual quiz tests understanding of heap state changes during extraction and bubbling down.

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 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 all elements smaller than the root

Solution

1. Step 1: Understand the extract min operation

   When we remove the minimum element (root) from a min-heap, the last element is moved to the root position.

2. Step 2: Apply bubble down to restore heap property

   The bubble down operation moves this new root element down the tree by swapping it with the smaller child until the heap property is restored.

3. Final Answer:

   To restore the 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 by pushing root down [OK]

Common Mistakes:

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

2. Which of the following C# code snippets correctly swaps the root element with its smaller child during bubble down in a min-heap?

easy

A. int temp = heap[i]; heap[i] = heap[child]; heap[child] = heap[i];

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

C. swap(heap[i], heap[child]);

D. int temp = heap[i]; heap[i] = heap[child]; heap[child] = temp;

Solution

1. Step 1: Identify correct swap syntax in C#

   int temp = heap[i]; heap[i] = heap[child]; heap[child] = temp; uses a temporary variable to swap two elements correctly, which is the standard way in C#.

2. Step 2: Check other options for correctness

   B: heap[i] = heap[child]; heap[child] = heap[i]; assigns values incorrectly causing data loss. C: swap(heap[i], heap[child]); is invalid syntax in C#. D: int temp = heap[i]; heap[i] = heap[child]; heap[child] = heap[i]; uses temp but assigns heap[child] the updated heap[i] value, causing no swap and data loss.

3. Final Answer:

   int temp = heap[i]; heap[i] = heap[child]; heap[child] = temp; -> Option D

4. Quick Check:

   Use temp variable to swap in C# [OK]

Hint: Use temp variable to swap array elements [OK]

Common Mistakes:

• Trying to swap without temp variable
• Using invalid syntax like swap() function
• Forgetting to use temp in the final assignment

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

medium

A. [5, 7, 3, 10]

B. [3, 5, 7, 10]

C. [3, 7, 5, 10]

D. [5, 3, 7, 10]

Solution

1. Step 1: Extract min and replace root

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

2. Step 2: Bubble down 7 to restore 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, which is larger, so stop.

3. Final Answer:

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

4. Quick Check:

   Extract min + bubble down = [3,5,7,10] [OK]

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

Common Mistakes:

• Not moving last element to root before bubble down
• Swapping with wrong child (larger instead of smaller)
• Stopping bubble down too early

4. Consider this bubble down code snippet for a max-heap in C#:

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

What is the bug if the heap array is empty (size = 0) and we call BubbleDown(heap, 0, 0)?

medium

A. Infinite recursion occurs

B. Heap property is violated after call

C. No bug; function exits immediately

D. Index out of range error when accessing heap[left]

Solution

1. Step 1: Analyze execution with size=0

   i=0, left=1, right=2. if(1 < 0 && ...) false due to short-circuit, no access to heap[1] or heap[0]. Similarly for right.

2. Step 2: Confirm safe exit

   largest=0 == i, no swap or recursion. Function exits immediately without any array access.

3. Final Answer:

   No bug; function exits immediately -> Option C

4. Quick Check:

   Short-circuit prevents access on empty heap [OK]

Hint: Rely on short-circuit evaluation for bounds safety [OK]

Common Mistakes:

• Misunderstanding C# short-circuit evaluation
• Assuming heap[largest] is always accessed
• Overlooking that no array access occurs

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

hard

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

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

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

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

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 to restore max-heap

   Children: 30 (idx1), 40 (idx2). Largest is 40. Swap 35 and 40: [40, 30, 35, 10, 20]. Now at idx2 (35), children idx5 and 6 >= size 5, no children. Stop.

3. Final Answer:

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

4. Quick Check:

   Extract max + bubble down = [40,30,35,10,20] [OK]

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

Common Mistakes:

• Swapping with smaller child in max-heap
• Incorrectly identifying children during bubble down
• Not moving last element to root before bubble down