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

Concept Flow - Heap Extract Min or Max Bubble Down

Start: Root node to remove

↓

Replace root with last element

↓

Remove last element from heap

↓

Set current = root

↓

Compare current with children

↓

Swap with smaller/larger child

↓

Update current to child

↓

Repeat until heap property restored

↓

Done

This flow shows how the root element is removed and replaced by the last element, then the heap property is restored by bubbling down the new root.

Execution Sample

DSA C

int extractMin(int heap[], int *size) {
    int min = heap[0];
    heap[0] = heap[*size - 1];
    (*size)--;
    bubbleDown(heap, *size, 0);
    return min;
}

Extracts the minimum element from a min-heap by replacing root with last element and bubbling down.

Execution Table

Step	Operation	Heap Array	Pointer Changes	Visual State
1	Initial heap	[10, 15, 30, 40, 50, 100, 40]	head = 0, size = 7	Array: [10, 15, 30, 40, 50, 100, 40] Tree: 10 / \ 15 30 / \ / \ 40 50 100 40
2	Extract min: remove root 10	[40, 15, 30, 40, 50, 100, 40]	head replaced with last element (index 6)	Array after replace root with last element: [40, 15, 30, 40, 50, 100, 40] Tree: 40 / \ 15 30 / \ / \ 40 50 100 40
3	Remove last element (index 6)	[40, 15, 30, 40, 50, 100]	size decremented to 6	Array size reduced: [40, 15, 30, 40, 50, 100] Tree: 40 / \ 15 30 / \ / 40 50 100
4	Bubble down from root (index 0)	[40, 15, 30, 40, 50, 100]	current = 0	Start bubble down at root 40
5	Compare children 15 (index 1) and 30 (index 2)	[40, 15, 30, 40, 50, 100]	smaller child = 15 at index 1	Children: 15 and 30, smaller is 15
6	40 > 15? Yes, swap	[15, 40, 30, 40, 50, 100]	swap indices 0 and 1, current = 1	After swap: [15, 40, 30, 40, 50, 100] Tree: 15 / \ 40 30 / \ / 40 50 100
7	Compare children of index 1: 40 (index 3) and 50 (index 4)	[15, 40, 30, 40, 50, 100]	smaller child = 40 at index 3	Children: 40 and 50, smaller is 40
8	40 > 40? No, stop bubble down	[15, 40, 30, 40, 50, 100]	bubble down ends	Heap property restored

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 6	After Step 8
heap array	[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]
size	7	7	6	6	6
current index	N/A	N/A	N/A	1	1

Key Moments - 3 Insights

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

Replacing root with last element keeps the heap complete (no gaps). Then bubbling down restores heap order. See execution_table step 2 and 3.

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

To maintain heap property, current must be smaller (min-heap) than both children. We swap with the smaller child if current is bigger. See execution_table steps 5 and 6.

When does the bubble down process stop?

It stops when current node is smaller than both children or has no children. See execution_table step 8 where 40 is not greater than 40.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the heap array after the swap?

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, 50, 40, 100]

💡 Hint

Check the 'Heap Array' column in execution_table row with Step 6.

At which step does the size of the heap decrease?

A Step 2

B Step 3

C Step 5

D Step 8

💡 Hint

Look at the 'size' variable in variable_tracker after each step.

If the last element was larger than the root, how would the bubble down steps change?

A Bubble down would not happen, heap property already holds

B Bubble down would swap root with larger child

C Bubble down would swap root with smaller child multiple times

D Heap size would increase

💡 Hint

Bubble down only swaps if current node is greater than children (see execution_table step 8).

Concept Snapshot

Heap Extract Min/Max Bubble Down:
- Remove root (min or max)
- Replace root with last element
- Decrease heap size
- Bubble down: swap with smaller (min-heap) or larger (max-heap) child
- Stop when heap property restored

Full Transcript

Heap extract min or max removes the root element from the heap. To keep the heap complete, the last element replaces the root. Then the heap size decreases by one. The new root may violate the heap property, so we bubble it down by comparing it with its children. If the root is larger than a child (min-heap), we swap it with the smaller child and continue. This repeats until the root is smaller than both children or has no children. This process restores the heap property while maintaining completeness.

Practice

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

easy

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

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

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 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 smaller children.

3. Final Answer:

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

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
• Assuming bubble down only swaps root with last element
• Confusing bubble down with bubble up

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

easy

A. temp = heap[i]; heap[i] = heap[j]; heap[j] = temp;

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

C. heap[i], heap[j] = heap[j], heap[i];

D. heap[i] <-> heap[j];

Solution

1. Step 1: Recognize C swap syntax

   In C, swapping requires a temporary variable to hold one value during exchange.

2. Step 2: Verify temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; uses temp variable correctly

   temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; uses a temporary variable to swap values correctly, while others use invalid or non-C syntax.

3. Final Answer:

   temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; -> Option A

4. Quick Check:

   C swap needs temp variable [OK]

Hint: Use temp variable to swap in C [OK]

Common Mistakes:

• Using Python or pseudocode swap syntax in C
• Trying to swap without temp variable
• Using invalid operators like <->

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

medium

A. [4, 7, 5, 10, 6]

B. [5, 4, 6, 10, 7]

C. [6, 4, 5, 10, 7]

D. [4, 6, 5, 10, 7]

Solution

1. Step 1: Remove root and replace with last element

   Remove 2, move last element 6 to root: [6, 4, 5, 10, 7]

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

   Compare 6 with children 4 and 5; swap with smallest child 4: [4, 6, 5, 10, 7]. Next, 6's children are 10 and 7, both larger, so stop.

3. Final Answer:

   [4, 6, 5, 10, 7] -> Option D

4. Quick Check:

   Bubble down swaps with smaller child [OK]

Hint: Replace root with last, then bubble down [OK]

Common Mistakes:

• Not swapping with the smallest child
• Stopping bubble down too early
• Replacing root incorrectly

4. Consider this bubble down code snippet for a max-heap in C. What is the bug?

void bubbleDown(int heap[], int size, int i) {
  int largest = i;
  int left = 2*i + 1;
  int right = 2*i + 2;
  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, size, largest);
  }
}

medium

A. No bug, code correctly bubbles down in max-heap

B. Left and right child indices calculation is wrong

C. Recursive call should be bubbleDown(heap, size, i) instead of largest

D. Swapping should happen only if heap[i] < heap[largest]

Solution

1. Step 1: Check child index calculations

   Left = 2*i+1 and right = 2*i+2 are correct for zero-based heap arrays.

2. Step 2: Verify bubble down logic

   Code finds largest among node and children, swaps if needed, then recurses on swapped child. This matches max-heap bubble down logic.

3. Final Answer:

   No bug, code correctly bubbles down in max-heap -> Option A

4. Quick Check:

   Correct child indices and recursion [OK]

Hint: Check child indices and recursion carefully [OK]

Common Mistakes:

• Confusing left/right child index formulas
• Wrong recursive call index
• Swapping condition misunderstanding

5. You have a max-heap represented by the array [20, 18, 15, 10, 12, 9, 8]. After extracting the maximum element and performing bubble down, what is the final heap array?

hard

A. [18, 12, 15, 10, 9, 8]

B. [18, 10, 15, 8, 12, 9]

C. [18, 12, 15, 10, 8, 9]

D. [18, 15, 12, 10, 9, 8]

Solution

1. Step 1: Remove root and replace with last element

   Remove 20, move last element 8 to root: [8, 18, 15, 10, 12, 9]

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

   Compare 8 with children 18 and 15; swap with largest child 18: [18, 8, 15, 10, 12, 9]. Next, 8's children are 10 and 12; swap with largest child 12: [18, 12, 15, 10, 8, 9]. Now 8's children are out of range, stop.

3. Final Answer:

   [18, 12, 15, 10, 8, 9] -> Option C

4. Quick Check:

   Bubble down swaps with largest child until heap property restored [OK]

Hint: Replace root with last, bubble down swapping largest child [OK]

Common Mistakes:

• Swapping with smaller child instead of largest
• Stopping bubble down too early
• Incorrectly replacing root element