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 value and then push that value down to restore the heap order.

Analogy: Imagine a pyramid of blocks where the top block is removed. To keep the pyramid stable, you take the bottom block and move it down step by step to the right place.

       [10]
      /     \
   [15]     [20]
   /  \     /  \
 [30] [40] [50] [60]

Heap array: [10, 15, 20, 30, 40, 50, 60]

Dry Run Walkthrough

Input: Heap array: [10, 15, 20, 30, 40, 50, 60], extract min (remove 10)

Goal: Remove the smallest element (root) and restore heap order by bubbling down

Step 1: Remove root 10, replace it with last element 60

[60, 15, 20, 30, 40, 50] (60 is at root, heap may be invalid)

Why: We remove the top and put last element at root to keep complete tree shape

Step 2: Compare 60 with children 15 and 20; swap with smallest child 15

[15, 60, 20, 30, 40, 50]

Why: To restore min-heap property, bubble down 60 by swapping with smaller child

Step 3: Compare 60 with children 30 and 40; swap with smallest child 30

[15, 30, 20, 60, 40, 50]

Why: Continue bubbling down 60 to correct position

Step 4: 60 has no children smaller than itself; stop bubbling down

[15, 30, 20, 60, 40, 50]

Why: Heap property restored, no further swaps needed

Result:

[15, 30, 20, 60, 40, 50] (min 10 extracted)

Annotated Code

DSA C

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void bubbleDown(int heap[], int size, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    // Check if left child exists and is smaller
    if (left < size && heap[left] < heap[smallest]) {
        smallest = left;
    }

    // Check if right child exists and is smaller
    if (right < size && heap[right] < heap[smallest]) {
        smallest = right;
    }

    // If smallest is not current index, swap and continue bubbling down
    if (smallest != index) {
        swap(&heap[index], &heap[smallest]);
        bubbleDown(heap, size, smallest); // recursive call
    }
}

int extractMin(int heap[], int *size) {
    if (*size <= 0) {
        return -1; // empty heap
    }

    int root = heap[0];
    heap[0] = heap[*size - 1]; // move last element to root
    (*size)--;
    bubbleDown(heap, *size, 0); // restore heap property
    return root;
}

void printHeap(int heap[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d", heap[i]);
        if (i != size - 1) {
            printf(" -> ");
        }
    }
    printf(" -> null\n");
}

int main() {
    int heap[] = {10, 15, 20, 30, 40, 50, 60};
    int size = 7;

    printf("Original heap:\n");
    printHeap(heap, size);

    int min = extractMin(heap, &size);
    printf("Extracted min: %d\n", min);

    printf("Heap after extractMin and bubble down:\n");
    printHeap(heap, size);

    return 0;
}

heap[0] = heap[*size - 1]; // move last element to root

Replace root with last element to maintain complete tree shape

(*size)--;

Reduce heap size after removing root

bubbleDown(heap, *size, 0); // restore heap property

Push down the new root to correct position to restore min-heap

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

Find smaller child to swap with

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

Check right child for smaller value

if (smallest != index) { swap(&heap[index], &heap[smallest]); bubbleDown(heap, size, smallest); }

Swap with smaller child and continue bubbling down recursively

Output

Original heap:

10 -> 15 -> 20 -> 30 -> 40 -> 50 -> 60 -> null

Extracted min: 10

Heap after extractMin and bubble down:

15 -> 30 -> 20 -> 60 -> 40 -> 50 -> null

Complexity Analysis

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

Space: O(log n) due to recursive calls in bubbleDown; can be O(1) if implemented iteratively

vs Alternative: Naive approach would reorder the entire heap which is O(n), bubble down is efficient by only fixing one path

Edge Cases

Empty heap

extractMin returns -1 indicating no element to remove

DSA C

if (*size <= 0) { return -1; }

Heap with one element

extractMin removes the only element and heap becomes empty

DSA C

(*size)--;

Heap where last element is larger than root's children

bubbleDown swaps last element down to correct position restoring heap

DSA C

if (smallest != index) { swap(...) bubbleDown(...); }

When to Use This Pattern

When you need to remove the top element from a heap and restore order, use bubble down to fix the heap 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 element from a heap and restores heap order by pushing down the replacement element.

Use when extracting min or max from a heap to maintain heap structure efficiently.

The key is to swap the root with the smaller (or larger) child repeatedly until heap property 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 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