Heap Extract Min or Max Bubble Down in DSA Go

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 in front but might be shorter, so they move down the line until everyone is taller behind them.

       1
      / \
     3   5
    / \  /
   7  9 8

(Heap as a tree with min at root)

Dry Run Walkthrough

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

Goal: Remove the smallest element (1) and restore heap order by pushing down the replacement

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

[8, 3, 5, 7, 9] (array form of heap)

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

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

[3, 8, 5, 7, 9]

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

Step 3: Compare 8 with its new children 7 and 9; swap with smallest child 7

[3, 7, 5, 8, 9]

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

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

[3, 7, 5, 8, 9]

Why: Reached leaf, heap order restored

Result:

[3, 7, 5, 8, 9] (heap after extract min and bubble down)

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type MinHeap struct {
	arr []int
}

func (h *MinHeap) bubbleDown(index int) {
	n := len(h.arr)
	for {
		left := 2*index + 1
		right := 2*index + 2
		smallest := index

		if left < n && h.arr[left] < h.arr[smallest] {
			smallest = left
		}
		if right < n && h.arr[right] < h.arr[smallest] {
			smallest = right
		}

		if smallest == index {
			break // heap property restored
		}

		h.arr[index], h.arr[smallest] = h.arr[smallest], h.arr[index]
		index = smallest // continue bubbling down
	}
}

func (h *MinHeap) ExtractMin() (int, bool) {
	n := len(h.arr)
	if n == 0 {
		return 0, false // empty heap
	}
	min := h.arr[0]
	h.arr[0] = h.arr[n-1] // move last to root
	h.arr = h.arr[:n-1]   // remove last
	h.bubbleDown(0)       // fix heap
	return min, true
}

func main() {
	h := MinHeap{arr: []int{1, 3, 5, 7, 9, 8}}
	min, ok := h.ExtractMin()
	if ok {
		fmt.Printf("Extracted min: %d\n", min)
		fmt.Printf("Heap after extract: %v\n", h.arr)
	} else {
		fmt.Println("Heap is empty")
	}
}

h.arr[0] = h.arr[n-1] // move last to root

Replace root with last element to keep complete tree shape

h.arr = h.arr[:n-1] // remove last

Remove last element since it's moved to root

h.bubbleDown(0) // fix heap

Restore heap order by pushing down the new root

if left < n && h.arr[left] < h.arr[smallest] { smallest = left }

Find smaller child to swap with

if right < n && h.arr[right] < h.arr[smallest] { smallest = right }

Check right child for smaller value

if smallest == index { break }

Stop if heap property is restored

h.arr[index], h.arr[smallest] = h.arr[smallest], h.arr[index]

Swap current node with smaller child

index = smallest // continue bubbling down

Move down to child's position

Output

Extracted min: 1

Heap after extract: [3 7 5 8 9]

Complexity Analysis

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

Space: O(1) because we do swaps in place without extra storage

vs Alternative: Naive approach would reorder the entire heap or array, costing O(n log n), so bubble down is much faster

Edge Cases

empty heap

ExtractMin returns false and zero value, no crash

DSA Go

if n == 0 { return 0, false // empty heap }

heap with one element

ExtractMin returns that element and heap becomes empty

DSA Go

h.arr = h.arr[:n-1]   // remove last

heap where last element is larger than root

Bubble down swaps as needed to restore heap order

DSA Go

bubbleDown function swaps with smaller child until heap property restored

When to Use This Pattern

When you see a problem asking to remove the top element from a heap and keep it valid, use extract + 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 remove the last element after moving it to root
Fix: Slice the array to remove last element after replacement

Summary

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

Use when you want to extract min or max from a heap and keep it valid.

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

Practice

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

easy

A. To add a new element at the end of the heap

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

C. To swap the minimum element with the maximum element

D. To remove all leaf nodes from the heap

Solution

1. Step 1: Understand extract-min operation

   When the minimum element (root) is removed, the last element is moved to the root.

2. Step 2: Apply bubble down to restore heap

   The bubble down moves this element down the tree to restore the min-heap property.

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 from root after removal [OK]

Common Mistakes:

• Thinking bubble down adds elements
• Confusing bubble down with bubble up
• Believing bubble down swaps min and max

2. Which of the following Go code snippets correctly performs the bubble down operation for a min-heap starting at index i in slice heap?

easy

A. for {
left := 2*i + 1
right := 2*i + 2
smallest := i
if left < len(heap) && heap[left] < heap[smallest] {
smallest = left
}
if right < len(heap) && heap[right] < heap[smallest] {
smallest = right
}
if smallest == i {
break
}
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
}

B. for i < len(heap) {
left := 2*i
right := 2*i + 1
if heap[left] > heap[right] {
heap[i], heap[left] = heap[left], heap[i]
i = left
} else {
heap[i], heap[right] = heap[right], heap[i]
i = right
}
}

C. for i > 0 {
parent := (i - 1) / 2
if heap[i] < heap[parent] {
heap[i], heap[parent] = heap[parent], heap[i]
i = parent
} else {
break
}
}

D. for {
left := 2*i + 1
right := 2*i + 2
largest := i
if left < len(heap) && heap[left] > heap[largest] {
largest = left
}
if right < len(heap) && heap[right] > heap[largest] {
largest = right
}
if largest == i {
break
}
heap[i], heap[largest] = heap[largest], heap[i]
i = largest
}

Solution

1. Step 1: Identify bubble down for min-heap

   Bubble down compares current node with children and swaps with smallest child.

2. Step 2: Check code correctness

   for { left := 2*i + 1 right := 2*i + 2 smallest := i if left < len(heap) && heap[left] < heap[smallest] { smallest = left } if right < len(heap) && heap[right] < heap[smallest] { smallest = right } if smallest == i { break } heap[i], heap[smallest] = heap[smallest], heap[i] i = smallest } correctly finds smallest child and swaps until heap property is restored.

3. Final Answer:

   Option A code snippet correctly implements bubble down for min-heap -> Option A

4. Quick Check:

   Min-heap bubble down uses smallest child swap [OK]

Hint: Bubble down swaps with smallest child in min-heap [OK]

Common Mistakes:

• Using 1-based indexing instead of 0-based
• Swapping with largest child in min-heap
• Using bubble up logic instead of bubble down

3. Given the min-heap represented by the slice heap := []int{2, 4, 5, 10, 8, 15}, what will be the heap slice after extracting the minimum element and performing bubble down?

medium

A. [4, 8, 5, 10, 15]

B. [5, 4, 15, 10, 8]

C. [4, 10, 5, 15, 8]

D. [8, 4, 5, 10, 15]

Solution

1. Step 1: Remove min and replace root

   Remove 2 (root), move last element 15 to root: [15,4,5,10,8]

2. Step 2: Bubble down 15

   Compare 15 with children 4 and 5; swap with 4 (smallest). Now heap: [4,15,5,10,8]. Next, bubble down 15 at index 1: children 10 and 8; swap with 8 (smallest). Final heap: [4,8,5,10,15]

3. Final Answer:

   [4, 8, 5, 10, 15] -> Option A

4. Quick Check:

   Extract min + bubble down = [4,8,5,10,15] [OK]

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

Common Mistakes:

• Not swapping with smallest child first
• Forgetting to move last element to root
• Swapping with larger child

4. Consider the following Go code snippet for bubble down in a max-heap. Identify the bug that causes incorrect heap after extraction:

func bubbleDown(heap []int, i int) {
  for {
    left := 2*i + 1
    right := 2*i + 2
    largest := i
    if left < len(heap) && heap[left] < heap[largest] {
      largest = left
    }
    if right < len(heap) && heap[right] < heap[largest] {
      largest = right
    }
    if largest == i {
      break
    }
    heap[i], heap[largest] = heap[largest], heap[i]
    i = largest
  }
}

medium

A. The loop condition should be 'while i > 0' instead of infinite loop

B. The indices for left and right children are incorrect

C. Swapping elements should be done after the loop ends

D. The comparisons use '<' instead of '>' for max-heap

Solution

1. Step 1: Understand max-heap bubble down logic

   In max-heap, bubble down swaps with the largest child, so comparisons should find the largest value.

2. Step 2: Identify incorrect comparison operators

   The code uses '<' to find smaller child, which is wrong for max-heap; it should use '>' to find largest child.

3. Final Answer:

   The comparisons use '<' instead of '>' for max-heap -> Option D

4. Quick Check:

   Max-heap bubble down uses '>' comparisons [OK]

Hint: Max-heap bubble down compares with '>' not '<' [OK]

Common Mistakes:

• Using wrong comparison operators for heap type
• Incorrect child index calculations
• Misplacing swap inside or outside loop

5. You have a max-heap represented as heap := []int{50, 30, 40, 10, 20, 35}. After extracting the maximum element and performing bubble down, what will be the resulting heap slice?

hard

A. [35, 30, 40, 10, 20]

B. [30, 20, 35, 10, 40]

C. [40, 30, 35, 10, 20]

D. [40, 30, 35, 20, 10]

Solution

1. Step 1: Remove max and replace root

   Remove 50 (root), move last element 35 to root: [35,30,40,10,20]

2. Step 2: Bubble down 35

   Compare 35 with children 30 and 40; swap with 40 (largest). Now heap: [40,30,35,10,20]. Next, bubble down 35 at index 2: children indices 5 and 6 do not exist (len=5), so stop. This restores the max-heap property.

3. Final Answer:

   [40, 30, 35, 10, 20] -> Option C

4. Quick Check:

   Extract max + bubble down = [40,30,35,10,20] [OK]

Hint: Swap with largest child repeatedly until heap property restored [OK]

Common Mistakes:

• Not swapping with largest child first
• Stopping bubble down too early
• Ignoring heap property for children