Heap Extract Min or Max Bubble Down in DSA C#

Mental Model

When we remove the top value from a heap, we replace it with the last item and then push it down to fix the heap order.

Analogy: Imagine a line of kids holding balloons by height order. If the tallest kid leaves, the last kid steps up and moves down the line until everyone is in order again.

       [10]
      /     \
   [15]     [20]
   /  \     /  \
 [17] [25] [30] [40]

Top is 10 (min heap).

Dry Run Walkthrough

Input: min heap: [10, 15, 20, 17, 25, 30, 40], extract min

Goal: Remove the smallest value (root) and restore heap order by pushing down the new root.

Step 1: Remove root 10 and replace it with last element 40

[40, 15, 20, 17, 25, 30]

Why: We remove the top and fill the gap with the last element to keep the tree complete.

Step 2: Compare 40 with children 15 and 20; swap with smaller child 15

[15, 40, 20, 17, 25, 30]

Why: To restore min heap, parent must be smaller than children, so 40 moves down.

Step 3: Compare 40 with children 17 and 25; swap with smaller child 17

[15, 17, 20, 40, 25, 30]

Why: Continue pushing down 40 to maintain heap order.

Step 4: 40 has no children smaller than itself, stop bubbling down

[15, 17, 20, 40, 25, 30]

Why: Heap order restored; 40 is in correct position.

Result:

[15, 17, 20, 40, 25, 30] after extracting min 10

Annotated Code

DSA C#

using System;

class MinHeap
{
    private int[] heap;
    private int size;

    public MinHeap(int capacity)
    {
        heap = new int[capacity];
        size = 0;
    }

    public void Insert(int val)
    {
        heap[size] = val;
        int current = size;
        size++;
        while (current > 0 && heap[current] < heap[Parent(current)])
        {
            Swap(current, Parent(current));
            current = Parent(current);
        }
    }

    public int ExtractMin()
    {
        if (size == 0) throw new InvalidOperationException("Heap is empty");
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        BubbleDown(0);
        return min;
    }

    private void BubbleDown(int index)
    {
        int smallest = index;
        int left = LeftChild(index);
        int right = RightChild(index);

        if (left < size && heap[left] < heap[smallest])
            smallest = left;

        if (right < size && heap[right] < heap[smallest])
            smallest = right;

        if (smallest != index)
        {
            Swap(index, smallest);
            BubbleDown(smallest);
        }
    }

    private int Parent(int i) => (i - 1) / 2;
    private int LeftChild(int i) => 2 * i + 1;
    private int RightChild(int i) => 2 * i + 2;

    private void Swap(int i, int j)
    {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public void PrintHeap()
    {
        for (int i = 0; i < size; i++)
            Console.Write(heap[i] + (i < size - 1 ? " -> " : " -> null"));
        Console.WriteLine();
    }
}

class Program
{
    static void Main()
    {
        MinHeap heap = new MinHeap(10);
        int[] values = {10, 15, 20, 17, 25, 30, 40};
        foreach (var v in values)
            heap.Insert(v);

        Console.WriteLine("Heap before extract min:");
        heap.PrintHeap();

        int min = heap.ExtractMin();
        Console.WriteLine($"Extracted min: {min}");

        Console.WriteLine("Heap after extract min and bubble down:");
        heap.PrintHeap();
    }
}

int min = heap[0];

store root value to return after extraction

heap[0] = heap[size - 1];

replace root with last element to keep tree complete

size--;

reduce heap size after removing last element

BubbleDown(0);

restore heap order by pushing down new root

if (left < size && heap[left] < heap[smallest]) smallest = left;

find smaller child to swap with

if (right < size && heap[right] < heap[smallest]) smallest = right;

compare right child as well

if (smallest != index) { Swap(index, smallest); BubbleDown(smallest); }

swap and continue bubbling down if needed

Output

Heap before extract min:

10 -> 15 -> 20 -> 17 -> 25 -> 30 -> 40 -> null

Extracted min: 10

Heap after extract min and bubble down:

15 -> 17 -> 20 -> 40 -> 25 -> 30 -> null

Complexity Analysis

Time: O(log n) because bubbling down moves down the height of the heap, which is log n

Space: O(1) because we only use a few variables and modify the heap in place

vs Alternative: Compared to rebuilding the heap from scratch (O(n)), bubbling down after extract is faster and more efficient.

Edge Cases

extract from empty heap

throws InvalidOperationException to prevent invalid operation

DSA C#

if (size == 0) throw new InvalidOperationException("Heap is empty");

extract from heap with one element

removes the only element and heap becomes empty without bubbling down

DSA C#

size--;

extract when last element is smaller than children

no swaps needed, bubbling down stops immediately

DSA C#

if (smallest != index) { ... } else stop

When to Use This Pattern

When you need to remove the top element from a heap and keep it a valid heap, use extract with bubble down to restore order efficiently.

Common Mistakes

Mistake: Not swapping with the smallest child during bubble down in a min heap
Fix: Always compare both children and swap with the smallest to maintain heap property

Mistake: Forgetting to reduce heap size after extraction
Fix: Decrease size before bubbling down to avoid accessing invalid elements

Summary

Removes the top (min or max) element from a heap and restores heap order by pushing down the replacement.

Use when you want to extract the smallest or largest element efficiently from a heap.

The key is to replace the root with the last element and then bubble it down by swapping with the smaller (or larger) child until heap order is restored.

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