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.