Heap Extract Min or Max Bubble Down in DSA Go - Execution Trace

Concept Flow - Heap Extract Min or Max Bubble Down

Start: Extract root (min or max)

↓

Replace root with last element

↓

Remove last element from heap

↓

Set current index = 0

↓

Compare current with children

↓

Swap with smaller/larger child

↓

Update current index to child's index

↓

Repeat until heap property restored

↓

Done

Extract the root element, replace it with the last element, then bubble down by swapping with the smaller (min-heap) or larger (max-heap) child until heap property is restored.

Execution Sample

DSA Go

heap := []int{10, 15, 30, 40, 50, 100, 40}
extractMin(heap)
// Extract root 10 and bubble down

Extract the minimum element (root) from a min-heap and restore heap property by bubbling down.

Execution Table

Step	Operation	Heap Array State	Pointer Changes	Visual State
1	Extract root (10)	[10, 15, 30, 40, 50, 100, 40]	root = 10	Tree: 10 / \ 15 30 / \ / \ 40 50 100 40
2	Replace root with last element (40)	[40, 15, 30, 40, 50, 100, 40]	root replaced by last element 40	Tree: 40 / \ 15 30 / \ / \ 40 50 100 40
3	Remove last element (index 6)	[40, 15, 30, 40, 50, 100]	last element removed	Tree: 40 / \ 15 30 / \ / 40 50 100
4	Compare root (40) with children (15, 30)	[40, 15, 30, 40, 50, 100]	current=0, left=1(15), right=2(30)	40 > 15 and 40 > 30, swap with smaller child 15
5	Swap root with left child (15)	[15, 40, 30, 40, 50, 100]	swap indices 0 and 1	Tree after swap: 15 / \ 40 30 / \ / 40 50 100
6	Update current index to 1	[15, 40, 30, 40, 50, 100]	current=1	Focus on node with value 40 at index 1
7	Compare current (40) with children (40, 50)	[15, 40, 30, 40, 50, 100]	left=3(40), right=4(50)	40 <= 40 and 40 <= 50, no swap needed
8	Heap property restored, stop	[15, 40, 30, 40, 50, 100]	no pointer changes	Final heap: 15 / \ 40 30 / \ / 40 50 100

💡 Heap property restored at step 7, no further swaps needed.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	Final
heap	[10, 15, 30, 40, 50, 100, 40]	[40, 15, 30, 40, 50, 100, 40]	[40, 15, 30, 40, 50, 100]	[15, 40, 30, 40, 50, 100]	[15, 40, 30, 40, 50, 100]	[15, 40, 30, 40, 50, 100]
current	N/A	0	0	0	1	1
left child index	N/A	1	1	1	3	3
right child index	N/A	2	2	2	4	4

Key Moments - 3 Insights

Why do we replace the root with the last element before bubbling down?

Replacing the root with the last element keeps the heap complete (no gaps). Then bubbling down restores the heap order. See execution_table step 2 and 3.

Why do we swap with the smaller child in a min-heap during bubble down?

Swapping with the smaller child ensures the smallest element moves up, maintaining min-heap property. See step 4 and 5 where 40 swaps with 15.

When do we stop bubbling down?

We stop when the current node is smaller or equal to both children (min-heap), meaning heap property is restored. See step 7 where no swap occurs.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the heap array state after the swap?

A [40, 15, 30, 40, 50, 100]

B [15, 40, 30, 40, 50, 100]

C [10, 15, 30, 40, 50, 100]

D [15, 30, 40, 40, 50, 100]

💡 Hint

Refer to the 'Heap Array State' column at step 5 in execution_table.

At which step does the current index update to 1 during bubble down?

A Step 6

B Step 5

C Step 4

D Step 7

💡 Hint

Check the 'Pointer Changes' column for current index updates.

If the last element was larger than the root, how would the heap array change after step 2?

A Root replaced by larger last element, likely no swaps needed

B Root remains unchanged

C Root replaced by larger last element, immediate swap with smaller child

D Heap size increases

💡 Hint

Think about bubble down logic when root is replaced by a larger value.

Concept Snapshot

Heap Extract Min or Max Bubble Down:
- Remove root (min or max element)
- Replace root with last element
- Remove last element from heap
- Bubble down: swap with smaller (min-heap) or larger (max-heap) child
- Repeat until heap property restored
- Maintains complete binary tree and heap order

Full Transcript

This visualization shows how to extract the root element from a heap and restore the heap property by bubbling down. First, the root is removed and replaced by the last element in the heap array to keep the tree complete. Then the last element is removed from the array. Starting at the root, we compare it with its children and swap with the smaller child in a min-heap if the root is larger. We update the current index to the swapped child's position and repeat this process until the heap property is restored, meaning the current node is smaller or equal to its children. The execution table tracks each step, showing the heap array state, pointer changes, and the visual tree structure. Key moments clarify why we replace the root with the last element, why we swap with the smaller child, and when to stop bubbling down. The visual quiz tests understanding of the heap array state after swaps, pointer updates, and the effect of replacing the root with a larger last element.

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