Heap Extract Min or Max Bubble Down in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Extract-Min on a Min-Heap

What is the state of the heap array after extracting the minimum element once from this min-heap?

Initial heap array (index 0 is root): [2, 5, 3, 8, 10, 15]

DSA Go

heap := []int{2, 5, 3, 8, 10, 15}
// Extract min operation
min := heap[0]
heap[0] = heap[len(heap)-1]
heap = heap[:len(heap)-1]
// Bubble down
index := 0
for {
  left := 2*index + 1
  right := 2*index + 2
  smallest := index
  if left < len(heap) && heap[left] < heap[smallest] {
    smallest = left
  }
  if right < len(heap) && heap[right] < heap[smallest] {
    smallest = right
  }
  if smallest == index {
    break
  }
  heap[index], heap[smallest] = heap[smallest], heap[index]
  index = smallest
}
fmt.Println(heap)

A [3, 5, 15, 8, 10]

B [5, 8, 3, 10, 15]

C [3, 5, 10, 8, 15]

D [5, 3, 8, 10, 15]

💡 Hint

Remember to replace the root with the last element and then bubble down by swapping with the smaller child.

After removing 2, the last element 15 moves to root. Then bubble down swaps 15 with 3 (smaller child), and stops because the new position (index 2) has no children (left child at index 5 >= length 5). Final heap is [3, 5, 15, 8, 10].

❓ Predict Output

intermediate

Output of Extract-Max on a Max-Heap

Given this max-heap array:

[20, 18, 15, 10, 12, 9, 8]

What is the heap array after extracting the maximum element once?

DSA Go

heap := []int{20, 18, 15, 10, 12, 9, 8}
max := heap[0]
heap[0] = heap[len(heap)-1]
heap = heap[:len(heap)-1]
index := 0
for {
  left := 2*index + 1
  right := 2*index + 2
  largest := index
  if left < len(heap) && heap[left] > heap[largest] {
    largest = left
  }
  if right < len(heap) && heap[right] > heap[largest] {
    largest = right
  }
  if largest == index {
    break
  }
  heap[index], heap[largest] = heap[largest], heap[index]
  index = largest
}
fmt.Println(heap)

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

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

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

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

💡 Hint

After replacing root with last element, bubble down by swapping with the larger child.

After removing 20, 8 moves to root. It swaps with 18 (larger child), then at index 1 (now 8) swaps with 12 (larger child there), then stops. Final heap is [18, 12, 15, 10, 8, 9].

🔧 Debug

advanced

Identify the Bug in Bubble Down for Min-Heap

This Go code tries to bubble down after extract-min on a min-heap. What error will it cause when run?

DSA Go

heap := []int{1, 3, 6, 5, 9, 8}
heap[0] = heap[len(heap)-1]
heap = heap[:len(heap)-1]
index := 0
for {
  left := 2*index + 1
  right := 2*index + 2
  smallest := index
  if left < len(heap) && heap[left] > heap[smallest] {
    smallest = left
  }
  if right < len(heap) && heap[right] < heap[smallest] {
    smallest = right
  }
  if smallest == index {
    break
  }
  heap[index], heap[smallest] = heap[smallest], heap[index]
  index = smallest
}
fmt.Println(heap)

A No error, prints [3, 5, 6, 8, 9]

B Index out of range runtime error

C Logic error: heap property violated, wrong output

D Compilation error due to invalid syntax

💡 Hint

Check the comparison signs in the if conditions for choosing smallest child.

The first if uses '>' instead of '<' causing wrong child selection. This breaks min-heap property but no runtime error occurs.

🧠 Conceptual

advanced

Why Bubble Down is Needed After Extract-Min or Extract-Max?

After removing the root element from a heap and replacing it with the last element, why do we need to bubble down?

A To restore the heap property by moving the new root down to its correct position

B To sort the entire heap array in ascending order

C To remove duplicate elements from the heap

D To increase the size of the heap by adding new elements

💡 Hint

Think about what happens to the heap property after replacing the root.

Replacing the root with the last element may break the heap property. Bubble down moves this element down to restore the heap order.

❓ Predict Output

expert

Final Heap After Multiple Extract-Min Operations

Starting with this min-heap array:

[4, 7, 6, 10, 9, 15, 20]

Perform extract-min operation twice in a row. What is the heap array after these two extractions?

DSA Go

heap := []int{4, 7, 6, 10, 9, 15, 20}
for i := 0; i < 2; i++ {
  heap[0] = heap[len(heap)-1]
  heap = heap[:len(heap)-1]
  index := 0
  for {
    left := 2*index + 1
    right := 2*index + 2
    smallest := index
    if left < len(heap) && heap[left] < heap[smallest] {
      smallest = left
    }
    if right < len(heap) && heap[right] < heap[smallest] {
      smallest = right
    }
    if smallest == index {
      break
    }
    heap[index], heap[smallest] = heap[smallest], heap[index]
    index = smallest
  }
}
fmt.Println(heap)

A [6, 9, 15, 10, 20]

B [7, 9, 15, 10, 20]

C [6, 9, 20, 10, 15]

D [7, 10, 15, 9, 20]

💡 Hint

Perform extract-min twice carefully, bubbling down each time.

First extraction removes 4, heap becomes [6,7,15,10,9,20] after bubble down. Second extraction removes 6, heap becomes [7,9,15,10,20].

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