Heap Insert Operation Bubble Up in DSA Go - Build from Scratch

Heap Insert Operation Bubble Up

📖 Scenario: You are managing a priority queue for tasks using a min-heap. Each task has a priority number, and lower numbers mean higher priority.When you add a new task, you must place it correctly in the heap so the smallest priority is always at the top.

🎯 Goal: Build a min-heap insert operation that adds a new priority number and moves it up (bubble up) to keep the heap order.

📋 What You'll Learn

Create a slice called heap with initial values representing a min-heap

Create a variable called newPriority with the new task's priority number

Write a bubble up loop to insert newPriority into heap and maintain min-heap order

Print the final heap slice after insertion

💡 Why This Matters

🌍 Real World

Priority queues are used in task scheduling, network packet management, and event simulation where tasks with higher priority must be handled first.

💼 Career

Understanding heap insertions and bubble up operations is essential for roles in software development, especially in systems programming, backend services, and algorithm design.

1

Create initial min-heap slice

Create a slice called heap with these exact integer values: 2, 5, 8, 10, 15.

DSA Go

# Create a slice called heap with values 2, 5, 8, 10, 15
# Your code here

Hint

Use heap := []int{2, 5, 8, 10, 15} to create the slice.

2

Add new priority value

Create an integer variable called newPriority and set it to 4.

DSA Go

package main

import "fmt"

func main() {
    heap := []int{2, 5, 8, 10, 15}
    // Create newPriority variable and set to 4
    // Your code here
}

Hint

Use newPriority := 4 to create the variable.

3

Insert and bubble up new priority

Append newPriority to heap. Then use a for loop with variable index starting at the last element's index. Inside the loop, calculate parentIndex as (index - 1) / 2. While index > 0 and heap[index] < heap[parentIndex], swap heap[index] and heap[parentIndex], then update index = parentIndex. This will bubble up the new priority to maintain the min-heap property.

DSA Go

package main

import "fmt"

func main() {
    heap := []int{2, 5, 8, 10, 15}
    newPriority := 4
    // Append newPriority to heap
    // Use for loop with index to bubble up
    // Your code here
}

Hint

Remember to append first, then bubble up by swapping with parent while smaller.

4

Print the final heap slice

Write fmt.Println(heap) to print the heap slice after insertion and bubbling up.

DSA Go

package main

import "fmt"

func main() {
    heap := []int{2, 5, 8, 10, 15}
    newPriority := 4

    heap = append(heap, newPriority)
    index := len(heap) - 1

    for index > 0 {
        parentIndex := (index - 1) / 2
        if heap[index] < heap[parentIndex] {
            heap[index], heap[parentIndex] = heap[parentIndex], heap[index]
            index = parentIndex
        } else {
            break
        }
    }

    // Print the heap slice
    // Your code here
}

Hint

Use fmt.Println(heap) to show the final heap.

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