Heap Insert Operation Bubble Up in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the heap array after inserting 15?

Given a min-heap represented as an array, what is the state of the heap array after inserting the value 15 and performing bubble up?

DSA Go

heap := []int{10, 20, 30, 40, 50}
// Insert 15 and bubble up
heap = append(heap, 15)
// Bubble up logic here

A [10, 20, 15, 40, 50, 30]

B [10, 20, 30, 40, 50, 15]

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

D [15, 10, 30, 40, 50, 20]

💡 Hint

Remember that bubble up swaps the inserted element with its parent while it is smaller.

After inserting 15 at the end, it swaps with 30 (its parent) because 15 < 30, resulting in [10, 20, 15, 40, 50, 30]. No further swaps needed as 15 > 10.

🧠 Conceptual

intermediate

Why does bubble up stop during heap insertion?

In a min-heap insertion, bubble up stops when:

A The inserted element is greater than or equal to its parent

B The inserted element reaches the last index

C The inserted element is smaller than its parent

D The heap array is full

💡 Hint

Think about the heap property and when it is satisfied.

Bubble up stops when the inserted element is not smaller than its parent, meaning the min-heap property is restored.

🔧 Debug

advanced

Find the error in this bubble up code snippet

What error will this Go code cause during bubble up in a min-heap insertion?

DSA Go

func bubbleUp(heap []int, index int) {
    for index > 0 {
        parent := (index - 1) / 2
        if heap[index] > heap[parent] {
            heap[index], heap[parent] = heap[parent], heap[index]
            index = parent
        } else {
            break
        }
    }
}

A The code swaps when the child is smaller than the parent, which is correct

B The code causes an index out of range error

C The code never stops and causes an infinite loop

D The code swaps when the child is greater than the parent, breaking min-heap property

💡 Hint

Check the comparison operator in the if condition.

In a min-heap, bubble up should swap when the child is smaller than the parent. This code swaps when child is greater, which breaks the heap property.

❓ Predict Output

advanced

What is the heap array after inserting 5 into this max-heap?

Given a max-heap array, what is the state after inserting 5 and performing bubble up?

DSA Go

heap := []int{50, 30, 40, 10, 20}
// Insert 5 and bubble up
heap = append(heap, 5)
// Bubble up logic here

A [50, 30, 40, 10, 20, 10]

B [50, 30, 40, 10, 20, 50]

C [50, 30, 40, 10, 20, 5]

D [5, 50, 40, 10, 20, 30]

💡 Hint

In max-heap bubble up, swap only if the inserted element is greater than its parent.

5 is less than its parent 40, so no swaps occur. The heap remains [50, 30, 40, 10, 20, 5].

🚀 Application

expert

How many swaps occur when inserting 3 into this min-heap?

Given the min-heap array [4, 7, 8, 10, 15, 9], how many swaps happen when inserting 3 and bubbling up?

DSA Go

heap := []int{4, 7, 8, 10, 15, 9}
// Insert 3 and bubble up

A 3

B 2

C 1

D 0

💡 Hint

Count each swap as the inserted element moves up the heap.

Insert 3 at index 6. Parent index 2 (value 8), swap 3 and 8 (1 swap). New index 2, parent index 0 (value 4), 3 < 4, swap again (2 swaps). Stop at root.

Practice

1. What is the main purpose of the bubble up operation when inserting a new element into a min-heap?

easy

A. To move the new element down to the bottom of the heap

B. To remove the smallest element from the heap

C. To move the new element up until the heap property is restored

D. To sort all elements in ascending order

Solution

1. Step 1: Understand the heap property

   In a min-heap, every parent node must be smaller than its children.

2. Step 2: Purpose of bubble up

   When a new element is added at the end, bubble up moves it up to restore the heap property.

3. Final Answer:

   To move the new element up until the heap property is restored -> Option C

4. Quick Check:

   Bubble up fixes heap by moving new element up [OK]

Hint: Bubble up moves new element up to fix heap order [OK]

Common Mistakes:

• Thinking bubble up moves element down
• Confusing bubble up with removing elements
• Assuming bubble up sorts the entire heap

2. Which of the following Go code snippets correctly swaps a child and its parent during bubble up in a min-heap?

easy

A. heap[i], heap[parent] = heap[parent], heap[i]

B. heap[i] = heap[parent]

C. heap[parent] = heap[i]

D. swap(heap[i], heap[parent])

Solution

1. Step 1: Understand swapping in Go slices

   To swap two elements in a slice, assign them simultaneously.

2. Step 2: Check each option

   heap[i], heap[parent] = heap[parent], heap[i] uses simultaneous assignment to swap correctly; others do not swap both elements.

3. Final Answer:

   heap[i], heap[parent] = heap[parent], heap[i] -> Option A

4. Quick Check:

   Simultaneous assignment swaps elements [OK]

Hint: Use simultaneous assignment to swap two slice elements [OK]

Common Mistakes:

• Assigning one element without swapping
• Using undefined swap function
• Confusing assignment direction

3. Given the min-heap represented by the slice [2, 5, 3, 10], what will be the heap after inserting 1 and performing bubble up?

medium

A. [2, 5, 3, 10, 1]

B. [1, 2, 3, 10, 5]

C. [1, 5, 2, 10, 3]

D. [1, 2, 3, 5, 10]

Solution

1. Step 1: Insert 1 at the end

   Heap becomes [2, 5, 3, 10, 1].

2. Step 2: Bubble up 1

   Compare 1 with parent 5 (index 1), swap: [2, 1, 3, 10, 5]. Then compare 1 with parent 2 (index 0), swap: [1, 2, 3, 10, 5].

3. Final Answer:

   [1, 2, 3, 10, 5] -> Option B

4. Quick Check:

   Bubble up swaps until heap property restored [OK]

Hint: Insert at end, then swap up while smaller than parent [OK]

Common Mistakes:

• Not swapping with grandparent
• Leaving new element at the end
• Swapping with wrong parent index

4. Consider this Go code snippet for bubble up in a min-heap:

for i > 0 && heap[i] < heap[(i-1)/2] {
    heap[i], heap[(i-1)/2] = heap[(i-1)/2], heap[i]
    i = (i-1)/2
}

What is the bug in this code?

medium

A. No bug; the code correctly bubbles up the element

B. The loop condition should use <= instead of <

C. The index update should be i = i/2 instead of (i-1)/2

D. The parent index calculation should be (i-1)/2, but it is correct here

Solution

1. Step 1: Check parent index calculation

   Parent index in a binary heap is (i-1)/2, which is correctly used.

2. Step 2: Verify loop condition and index update

   Loop continues while current element is less than parent; index updates to parent correctly.

3. Final Answer:

   No bug; the code correctly bubbles up the element -> Option A

4. Quick Check:

   Parent index and swaps are correct [OK]

Hint: Parent index = (i-1)/2; loop swaps while child < parent [OK]

Common Mistakes:

• Miscomputing parent index
• Using wrong comparison operator
• Incorrect index update after swap

5. You have a max-heap represented by the slice [90, 70, 80, 40, 50, 60]. You insert 85 at the end and perform bubble up. What is the final heap after bubble up?

hard

A. [90, 85, 80, 40, 50, 60, 70]

B. [85, 70, 90, 40, 50, 60, 80]

C. [90, 70, 80, 40, 50, 60, 85]

D. [90, 70, 85, 40, 50, 60, 80]

Solution

1. Step 1: Insert 85 at the end

   Heap becomes [90, 70, 80, 40, 50, 60, 85].

2. Step 2: Bubble up 85 in max-heap

   Parent of index 6 is (6-1)/2 = 2 with value 80. Since 85 > 80, swap: [90, 70, 85, 40, 50, 60, 80]. Now index 2's parent is index 0 (90), 85 < 90, stop.

3. Final Answer:

   [90, 70, 85, 40, 50, 60, 80] -> Option D

4. Quick Check:

   Bubble up swaps while child > parent in max-heap [OK]

Hint: In max-heap, bubble up swaps while child > parent [OK]

Common Mistakes:

• Not swapping with parent when child is larger
• Stopping bubble up too early
• Confusing max-heap with min-heap rules