Heap Extract Min or Max Bubble Down in DSA C# - Time & Space Complexity

Time Complexity: Heap Extract Min or Max Bubble Down

O(log n)

Understanding Time Complexity

We want to understand how long it takes to remove the smallest or largest item from a heap and fix the heap order.

How does the time needed grow as the heap gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int ExtractMin()
{
    int min = heap[0];
    heap[0] = heap[heap.Count - 1];
    heap.RemoveAt(heap.Count - 1);
    BubbleDown(0);
    return min;
}

private void BubbleDown(int index)
{
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int smallest = index;

    if (left < heap.Count && heap[left] < heap[smallest])
        smallest = left;
    if (right < heap.Count && heap[right] < heap[smallest])
        smallest = right;

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

This code removes the smallest item from a min-heap and then moves the new root down to restore heap order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The recursive calls in BubbleDown that compare and swap nodes.
• How many times: At most once per level of the heap, moving down from root to leaf.

How Execution Grows With Input

Each step moves down one level in the heap tree, which grows slowly as the heap grows.

Input Size (n)	Approx. Operations
10	About 4 steps (levels)
100	About 7 steps
1000	About 10 steps

Pattern observation: The number of steps grows slowly, roughly with the height of the heap tree, which is much smaller than the number of items.

Final Time Complexity

Time Complexity: O(log n)

This means the time to fix the heap grows slowly, proportional to the height of the heap tree, as the heap gets bigger.

Common Mistake

[X] Wrong: "Extracting min takes constant time because we only remove the root."

[OK] Correct: Removing the root is quick, but restoring heap order by moving the new root down takes time proportional to the heap height, which grows with input size.

Interview Connect

Understanding this helps you explain how priority queues work efficiently and shows you can analyze tree-based algorithms clearly.

Self-Check

"What if we changed the heap to a binary search tree? How would the time complexity of extracting the minimum change?"

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