Heap Extract Min or Max Bubble Down in DSA Java

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 pyramid of blocks where the top block is removed. You take the bottom block and place it on top, then slide it down to its correct spot so the pyramid stays stable.

       1
      / \
     3   5
    / \  /
   7  9 8

Heap array: [1, 3, 5, 7, 9, 8]

Dry Run Walkthrough

Input: min-heap: [1, 3, 5, 7, 9, 8], extract min

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

Step 1: Remove root (1) and replace it with last element (8)

Heap array: [8, 3, 5, 7, 9]

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

Step 2: Compare 8 with children 3 and 5, swap with smallest child 3

Heap array: [3, 8, 5, 7, 9]

Why: 8 is bigger than 3, so swap to restore min-heap property

Step 3: Compare 8 with children 7 and 9, swap with smallest child 7

Heap array: [3, 7, 5, 8, 9]

Why: 8 is bigger than 7, so swap to maintain heap order

Step 4: 8 has no children now, stop bubbling down

Heap array: [3, 7, 5, 8, 9]

Why: Reached leaf, heap order restored

Result:

Heap array after extract min and bubble down: [3, 7, 5, 8, 9]
Extracted min: 1

Annotated Code

DSA Java

import java.util.Arrays;

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

    public MinHeap(int[] array) {
        heap = Arrays.copyOf(array, array.length);
        size = heap.length;
        buildHeap();
    }

    private void buildHeap() {
        for (int i = (size / 2) - 1; i >= 0; i--) {
            bubbleDown(i);
        }
    }

    public int extractMin() {
        if (size == 0) throw new IllegalStateException("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 = 2 * index + 1;
        int right = 2 * index + 2;

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

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

        if (smallest != index) {
            int temp = heap[index];
            heap[index] = heap[smallest];
            heap[smallest] = temp;
            bubbleDown(smallest);
        }
    }

    public void printHeap() {
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i]);
            if (i < size - 1) System.out.print(" -> ");
        }
        System.out.println(" -> null");
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 8};
        MinHeap minHeap = new MinHeap(array);
        System.out.print("Heap before extractMin: ");
        minHeap.printHeap();
        int extracted = minHeap.extractMin();
        System.out.println("Extracted min: " + extracted);
        System.out.print("Heap after extractMin: ");
        minHeap.printHeap();
    }
}

int min = heap[0];

store root value to return as extracted min

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

replace root with last element to maintain complete tree

size--;

reduce heap size after removal

bubbleDown(0);

restore heap order by pushing new root down

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 to find smallest

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

swap with smaller child and continue bubbling down

Output

Heap before extractMin: 1 -> 3 -> 5 -> 7 -> 9 -> 8 -> null

Extracted min: 1

Heap after extractMin: 3 -> 7 -> 5 -> 8 -> 9 -> null

Complexity Analysis

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

Space: O(1) because the operation modifies the heap in place without extra storage

vs Alternative: Naive approach would be to rebuild the heap from scratch after removal which is O(n), bubble down is more efficient

Edge Cases

empty heap

throws IllegalStateException because there is no element to extract

DSA Java

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

heap with one element

extractMin returns the only element and heap becomes empty

DSA Java

size--;

heap where last element is larger than root's children

bubble down stops immediately as heap order is already correct

DSA Java

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

When to Use This Pattern

When you need to remove the top element from a heap and keep the heap property, use extract min/max with bubble down to restore order efficiently.

Common Mistakes

Mistake: Not replacing the root with the last element before bubbling down
Fix: Always move the last element to the root position before starting bubble down

Mistake: Not checking if children indices are within heap size before comparing
Fix: Check left and right child indices are less than current heap size before accessing

Mistake: Stopping bubble down too early without swapping with the smallest child
Fix: Always swap with the smallest child if it is smaller than current node and continue bubbling down

Summary

Removes the root from a heap and restores heap order by pushing down the replacement element.

Use when you want to extract the minimum or maximum element from a heap efficiently.

The key is to replace the root with the last element and bubble it down to maintain the heap property.

Practice

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

easy

A. To remove all leaf nodes from 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 insert a new element at the bottom of the heap

Solution

1. Step 1: Understand the extract operation

   When we remove the min or max element (usually the root), the heap may lose its order property.

2. Step 2: Purpose of bubble down

   Bubble down moves the new root element down the tree to restore the heap property by swapping it with the smaller (min-heap) or larger (max-heap) child.

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 order after extraction [OK]

Hint: Bubble down fixes heap order after removing root [OK]

Common Mistakes:

• Thinking bubble down inserts new elements
• Assuming bubble down removes leaf nodes
• Believing bubble down only swaps root and last element

2. Which of the following Java method signatures correctly represents a bubble down operation for a min-heap stored in an array?

easy

A. void bubbleDown(int[] heap, int index, int size)

B. int bubbleDown(int[] heap, int size)

C. void bubbleDown(int index, int[] heap)

D. boolean bubbleDown(int[] heap, int index)

Solution

1. Step 1: Identify parameters needed for bubble down

   We need the heap array, the current index to bubble down from, and the size of the heap to avoid out-of-bounds.

2. Step 2: Match method signature

   void bubbleDown(int[] heap, int index, int size) has all parameters in correct order and returns void as bubble down modifies the heap in place.

3. Final Answer:

   void bubbleDown(int[] heap, int index, int size) -> Option A

4. Quick Check:

   Correct parameters and void return for bubble down [OK]

Hint: Bubble down needs array, index, and size parameters [OK]

Common Mistakes:

• Missing size parameter causing index errors
• Wrong return type expecting a value
• Incorrect parameter order

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

medium

A. [3, 5, 7, 10]

B. [5, 7, 3, 10]

C. [3, 7, 5, 10]

D. [5, 3, 7, 10]

Solution

1. Step 1: Remove min and replace root

   Remove 2 (min), replace root with last element 7: [7, 5, 3, 10]

2. Step 2: Bubble down from root

   Compare 7 with children 5 and 3; smallest is 3. Swap 7 and 3: [3, 5, 7, 10]. Now 7 has children 10 only, 7 < 10, so stop.

3. Final Answer:

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

4. Quick Check:

   Bubble down restores min-heap order [OK]

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

Common Mistakes:

• Not replacing root with last element 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. Identify the bug:

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

medium

A. The comparison operators should be < instead of > for max-heap

B. The left and right child indices calculation is incorrect

C. The recursive call should be bubbleDown(heap, index, size) instead of bubbleDown(heap, largest, size)

D. There is no bug; the code correctly performs bubble down

Solution

1. Step 1: Check child index calculations

   Left = 2*index+1 and right = 2*index+2 are correct for binary heap stored in array.

2. Step 2: Verify comparisons and recursion

   Comparisons use > for max-heap to find largest child. Recursive call uses largest index to continue bubbling down correctly.

3. Final Answer:

   There is no bug; the code correctly performs bubble down -> Option D

4. Quick Check:

   Child indices and recursion are correct [OK]

Hint: Check indices and recursion carefully; they are often correct [OK]

Common Mistakes:

• Confusing child index formulas
• Wrong comparison operators for max-heap
• Incorrect recursive call index

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

hard

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

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

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

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

Solution

1. Step 1: Extract max and replace root

   Remove 20, replace root with last element 8: [8, 18, 15, 10, 12, 9]

2. Step 2: Bubble down from root

   Compare 8 with children 18 and 15; largest is 18. Swap 8 and 18: [18, 8, 15, 10, 12, 9]. Now bubble down at index 1.

3. Step 3: Continue bubble down

   At index 1, children are 10 and 12; largest is 12. Swap 8 and 12: [18, 12, 15, 10, 8, 9]. At index 4, children do not exist, stop.

4. Final Answer:

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

5. Quick Check:

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

Hint: Replace root with last, swap down with largest child repeatedly [OK]

Common Mistakes:

• Not continuing bubble down after first swap
• Swapping with smaller child by mistake
• Forgetting to update heap size after extraction