Heap Insert Operation Bubble Up in DSA Go

Mental Model

When adding a new number to a heap, we put it at the end and then move it up until the heap rules are right again.

Analogy: Imagine a new player joining a team lineup at the back, then moving forward step by step if they are better than the player in front, until everyone is in the right order.

Heap as array:
[10, 15, 20, 17, 25]
Insert 13 at end:
[10, 15, 20, 17, 25, 13]
Index positions:
[0,  1,  2,  3,  4,  5]

Dry Run Walkthrough

Input: heap: [10, 15, 20, 17, 25], insert value 13

Goal: Add 13 and move it up until the heap property is restored

Step 1: Insert 13 at the end of the heap array

[10, 15, 20, 17, 25, 13]

Why: New value must be added at the end before fixing the heap

Step 2: Compare 13 with its parent 20; since 13 < 20, swap them

[10, 15, 13, 17, 25, 20]

Why: Smaller child should move up to maintain min-heap order

Step 3: Compare 13 with new parent 15; since 13 < 15, swap them

[10, 13, 15, 17, 25, 20]

Why: Smaller child should move up to maintain min-heap order

Step 4: Compare 13 with new parent 10; since 13 > 10, stop bubbling up

[10, 13, 15, 17, 25, 20]

Why: Heap property is restored, no more swaps needed

Result:

[10, 13, 15, 17, 25, 20]

Annotated Code

DSA Go

package main

import "fmt"

// MinHeap struct holds the heap array
type MinHeap struct {
	arr []int
}

// Insert adds a new value and bubbles it up to restore heap
func (h *MinHeap) Insert(val int) {
	h.arr = append(h.arr, val) // add at end
	current := len(h.arr) - 1
	for current > 0 {
		parent := (current - 1) / 2
		if h.arr[current] < h.arr[parent] {
			h.arr[current], h.arr[parent] = h.arr[parent], h.arr[current] // swap
			current = parent // move up
		} else {
			break // heap property restored
		}
	}
}

func main() {
	h := MinHeap{arr: []int{10, 15, 20, 17, 25}}
	fmt.Println("Before insert:", h.arr)
	h.Insert(13)
	fmt.Println("After insert:", h.arr)
}

h.arr = append(h.arr, val) // add at end

Add new value at the end of the heap array

current := len(h.arr) - 1

Start bubbling up from the last index

parent := (current - 1) / 2

Find parent index of current node

if h.arr[current] < h.arr[parent] {

Check if current value is smaller than parent to decide swap

h.arr[current], h.arr[parent] = h.arr[parent], h.arr[current] // swap

Swap current node with parent to move smaller value up

current = parent // move up

Update current index to parent's index to continue bubbling

else { break }

Stop bubbling when heap property is satisfied

Output

Before insert: [10 15 20 17 25]

After insert: [10 13 15 17 25 20]

Complexity Analysis

Time: O(log n) because in worst case the new element moves up the height of the heap

Space: O(1) because insertion is done in place without extra space

vs Alternative: Compared to rebuilding the heap from scratch (O(n)), bubbling up is faster for single insertions

Edge Cases

Insert into empty heap

Value is simply added as root with no bubbling

DSA Go

current > 0

Insert value larger than all existing values

Value stays at the end, no swaps happen

DSA Go

if h.arr[current] < h.arr[parent]

Insert duplicate value equal to parent

No swap since value is not smaller, heap property maintained

DSA Go

if h.arr[current] < h.arr[parent]

When to Use This Pattern

When you need to add an element to a heap and keep it ordered, use bubble up to fix the heap from bottom to top efficiently.

Common Mistakes

Mistake: Swapping with parent even when the current value is not smaller
Fix: Only swap if current value is strictly smaller than parent

Mistake: Not updating current index after swap, causing infinite loop
Fix: Update current to parent index after each swap

Mistake: Starting bubble up from wrong index
Fix: Always start from the last inserted element's index

Summary

It adds a new value to the heap and moves it up until the heap order is correct.

Use it when inserting a new element into a min-heap or max-heap to keep the heap property.

The key insight is that only the path from the inserted node to the root needs fixing by swapping with parents.

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