Heap Insert Operation Bubble Up in DSA C++ - 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?

It stops when the inserted element is greater than or equal to its parent or 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.

beginner

Show the parent index formula used during bubble up in a heap stored as an array.

Parent index = (child index - 1) / 2 (integer division). This formula helps find the parent node to compare during bubble up.

beginner

Why is bubble up necessary after inserting a new element at the end of the heap array?

Because inserting at the end may violate the heap property, bubble up fixes this by swapping the new element with its parent until the heap property is restored.

What does the bubble up operation do in a heap insert?

A Swaps the root with the last element

B Moves the new element up to restore heap property

C Removes the root element

D Deletes the last element

Bubble up moves the newly inserted element up to maintain the heap property.

In a max-heap, bubble up continues while the child is ____ than the parent.

A less

B equal

C greater

D not comparable

In a max-heap, bubble up swaps while the child is greater than the parent.

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

A 2

B 3

C 1

D 4

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

What is the worst-case time complexity of bubble up in a heap of size n?

A O(1)

B O(n)

C O(n log n)

D O(log n)

Bubble up takes O(log n) time because it moves up the height of the heap.

Where is the new element inserted before bubble up in a heap stored as an array?

A At the end of the array

B At the root

C In the middle of the array

D At the beginning of the array

New elements are inserted at the end of the array before bubble up.

Explain the bubble up operation during heap insert and why it is necessary.

Think about how the heap property might break and how bubble up fixes it.

Describe how to find the parent index of a node in a heap stored as an array and how this helps in bubble up.

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

Practice

1. What is the main purpose of the bubble up operation during a heap insert?

easy

A. To delete the root element of the heap

B. To move the new element to the bottom of the heap

C. To restore the heap property by moving the new element up if it is smaller than its parent

D. To sort all elements in ascending order

Solution

1. Step 1: Understand heap property

   In a min-heap, every parent node is smaller than its children. When inserting, this property might be violated.

2. Step 2: Purpose of bubble up

   The bubble up operation moves the newly inserted element up the tree if it is smaller than its parent, restoring the heap property.

3. Final Answer:

   To restore the heap property by moving the new element up if it is smaller than its parent -> Option C

4. Quick Check:

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

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

Common Mistakes:

• Thinking bubble up moves element down
• Confusing bubble up with deletion
• Assuming bubble up sorts entire heap

2. Which of the following C++ code snippets correctly performs the bubble up step after inserting a new element at the end of a min-heap vector heap?

easy

A. int i = heap.size() - 1; while (i > 0 && heap[i] < heap[(i - 1) / 2]) { std::swap(heap[i], heap[(i - 1) / 2]); i = (i - 1) / 2; }

B. int i = 0; while (i < heap.size() && heap[i] > heap[(2 * i) + 1]) { std::swap(heap[i], heap[(2 * i) + 1]); i = (2 * i) + 1; }

C. int i = heap.size() - 1; while (i > 0 && heap[i] > heap[(i - 1) / 2]) { std::swap(heap[i], heap[(i - 1) / 2]); i = (i - 1) / 2; }

D. int i = heap.size() - 1; while (i > 0 && heap[i] < heap[(2 * i) + 2]) { std::swap(heap[i], heap[(2 * i) + 2]); i = (2 * i) + 2; }

Solution

1. Step 1: Identify bubble up logic

   Bubble up compares the inserted element with its parent at index (i-1)/2 and swaps if smaller.

2. Step 2: Check each option

   int i = heap.size() - 1; while (i > 0 && heap[i] < heap[(i - 1) / 2]) { std::swap(heap[i], heap[(i - 1) / 2]); i = (i - 1) / 2; } correctly uses the parent index and swaps while the child is smaller. Others use wrong indices or wrong comparison.

3. Final Answer:

   int i = heap.size() - 1; while (i > 0 && heap[i] < heap[(i - 1) / 2]) { std::swap(heap[i], heap[(i - 1) / 2]); i = (i - 1) / 2; } -> Option A

4. Quick Check:

   Bubble up uses parent index (i-1)/2 and swaps if smaller [OK]

Hint: Parent index = (i-1)/2; swap if child smaller [OK]

Common Mistakes:

• Using child indices instead of parent
• Swapping when child is larger
• Starting index at 0 instead of last element

3. Given the min-heap represented by the vector heap = {2, 5, 8, 10, 15}, what will be the heap vector after inserting 1 and performing bubble up?

medium

A. [1, 2, 8, 10, 15, 5]

B. [1, 2, 5, 10, 15, 8]

C. [1, 5, 2, 10, 15, 8]

D. [2, 5, 8, 10, 15, 1]

Solution

1. Step 1: Insert 1 at the end

   Heap becomes [2, 5, 8, 10, 15, 1]. Index of 1 is 5.

2. Step 2: Bubble up 1

   Parent index = (5-1)/2 = 2. Compare heap[5]=1 with heap[2]=8. Since 1 < 8, swap. Heap: [2, 5, 1, 10, 15, 8]. Now i=2.

3. Step 3: Continue bubble up

   Parent index = (2-1)/2=0. Compare heap[2]=1 with heap[0]=2. Since 1 < 2, swap. Heap: [1, 5, 2, 10, 15, 8]. Now i=0, stop.

4. Final Answer:

   [1, 5, 2, 10, 15, 8] -> Option B

5. Quick Check:

   Bubble up swaps until heap property restored [OK]

Hint: Insert at end, swap with parent if smaller until root [OK]

Common Mistakes:

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

4. Consider the following code snippet for bubble up after inserting into a min-heap vector heap. Identify the error:

int i = heap.size() - 1;
while (i > 0 && heap[i] > heap[(i - 1) / 2]) {
    std::swap(heap[i], heap[(i - 1) / 2]);
    i = (i - 1) / 2;
}

medium

A. The comparison operator should be '<' instead of '>'

B. The loop should start from i = 0

C. The swap function is used incorrectly

D. The parent index calculation is wrong

Solution

1. Step 1: Understand bubble up condition

   In a min-heap, bubble up swaps when child is smaller than parent, so condition should be heap[i] < heap[parent].

2. Step 2: Identify error in code

   The code uses heap[i] > heap[parent], which is incorrect and will not restore min-heap property.

3. Final Answer:

   The comparison operator should be '<' instead of '>' -> Option A

4. Quick Check:

   Bubble up swaps when child < parent [OK]

Hint: Bubble up swaps if child smaller than parent [OK]

Common Mistakes:

• Using wrong comparison direction
• Starting loop at wrong index
• Miscalculating parent index

5. You have a max-heap represented by heap = {20, 15, 18, 10, 12, 17}. You insert 19 at the end and perform bubble up. What is the resulting heap vector?

hard

A. [20, 15, 18, 10, 12, 17, 19]

B. [20, 19, 18, 15, 12, 17, 10]

C. [19, 15, 20, 10, 12, 17, 18]

D. [20, 15, 19, 10, 12, 17, 18]

Solution

1. Step 1: Insert 19 at the end

   Heap becomes [20, 15, 18, 10, 12, 17, 19]. Index of 19 is 6.

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

   Parent index = (6-1)/2 = 2. Compare heap[6]=19 with heap[2]=18. Since 19 > 18, swap. Heap: [20, 15, 19, 10, 12, 17, 18]. Now i=2.

3. Step 3: Continue bubble up

   Parent index = (2-1)/2=0. Compare heap[2]=19 with heap[0]=20. Since 19 < 20, stop.

4. Final Answer:

   [20, 15, 19, 10, 12, 17, 18] -> Option D

5. Quick Check:

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

Hint: In max-heap, bubble up swaps if child bigger than parent [OK]

Common Mistakes:

• Using min-heap logic for max-heap
• Not swapping enough times
• Incorrect parent index calculation