Heap Insert Operation Bubble Up in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the purpose of the bubble up operation in a heap insert?

The bubble up operation restores the heap property by moving the newly inserted element up the tree until it is in the correct position.

beginner

In a min-heap, when does the bubble up operation stop during insertion?

It stops when the inserted element is greater than or equal to its parent or when it reaches the root of the heap.

intermediate

What is the time complexity of the bubble up operation in a heap insert?

The time complexity is O(log n), where n is the number of elements in the heap, because the element moves up at most the height of the heap.

intermediate

Explain the relationship between the child and parent indices in a heap array during bubble up.

For a child at index i, the parent index is (i-1)/2 (integer division). Bubble up compares the child with this parent to decide if swapping is needed.

beginner

Why is bubble up important for maintaining heap structure after insertion?

Because inserting at the end may break the heap property, bubble up fixes this by moving the new element up until the heap property is restored.

What is the first step after inserting a new element at the end of a heap array?

A Perform bubble up to restore heap property

B Remove the root element

C Sort the entire array

D Do nothing

After insertion at the end, bubble up moves the element up to maintain the heap property.

In a max-heap, bubble up swaps the inserted element with its parent if:

A Inserted element is smaller than parent

B Inserted element is larger than parent

C Inserted element is equal to parent

D Inserted element is at root

In max-heap, bubble up swaps when the child is larger than the parent to maintain max-heap property.

What is the parent index of the element at index 5 in a heap array?

A 3

B 1

C 2

D 4

Parent index = (5-1)/2 = 4/2 = 2.

Which of these best describes the heap property?

A Heap property does not depend on parent-child relationship

B Every parent is larger than its children in a min-heap

C Every child is larger than its parent in a max-heap

D Every parent is smaller than or equal to its children in a min-heap

In a min-heap, each parent node is smaller than or equal to its children.

What is the worst-case number of swaps during bubble up in a heap of size n?

A O(log n)

B O(n)

C O(1)

D O(n log n)

Bubble up swaps at most the height of the heap, which is O(log n).

Describe the bubble up process during heap insertion and why it is necessary.

Think about how the new element moves up to keep the heap order.

Explain how to calculate the parent index of a node in a heap stored as an array.

Remember the heap is a complete binary tree stored in an array.

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