Heap Insert Operation Bubble Up in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the heap array after inserting 15?

Given a max-heap represented as an array, what is the array after inserting the value 15 and performing bubble up?

DSA C++

std::vector<int> heap = {20, 18, 10, 12, 9, 8};
int value = 15;
// Insert value and bubble up
heap.push_back(value);
int i = heap.size() - 1;
while (i > 0) {
    int parent = (i - 1) / 2;
    if (heap[i] <= heap[parent]) break;
    std::swap(heap[i], heap[parent]);
    i = parent;
}
for (int v : heap) std::cout << v << " ";

A [20, 18, 10, 12, 9, 8, 15]

B [20, 18, 15, 12, 9, 8, 10]

C [20, 18, 10, 15, 9, 8, 12]

D [20, 15, 18, 12, 9, 8, 10]

💡 Hint

Remember to swap the inserted element with its parent while it is greater.

The inserted value 15 is placed at the end. It swaps with 10 (parent) because 15 > 10, then stops because 15 <= 20 (new parent). The final heap array is [20, 18, 15, 12, 9, 8, 10].

❓ Predict Output

intermediate

What is the heap after inserting 5 into this max-heap?

Starting with the max-heap array [30, 20, 15, 10, 8], what is the array after inserting 5 and performing bubble up?

DSA C++

std::vector<int> heap = {30, 20, 15, 10, 8};
int value = 5;
heap.push_back(value);
int i = heap.size() - 1;
while (i > 0) {
    int parent = (i - 1) / 2;
    if (heap[i] <= heap[parent]) break;
    std::swap(heap[i], heap[parent]);
    i = parent;
}
for (int v : heap) std::cout << v << " ";

A [30, 20, 15, 10, 8, 5]

B [30, 20, 15, 10, 5, 8]

C [30, 20, 15, 5, 8, 10]

D [30, 20, 15, 10, 8, 10]

💡 Hint

If the inserted value is smaller than its parent, no swaps happen.

The inserted value 5 is smaller than its parent 15, so no bubble up swaps occur. The heap array becomes [30, 20, 15, 10, 8, 5].

🔧 Debug

advanced

Identify the bug in this bubble up code snippet

What is the error in this bubble up code for a max-heap insert?

DSA C++

void bubbleUp(std::vector<int>& heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[index] <= heap[parent]) break;
        std::swap(heap[index], heap[parent]);
        index = parent;
    }
}

A The swap should be done only if heap[index] < heap[parent]

B The loop condition should be index >= 0

C Parent index calculation is wrong; should be (index - 1) / 2

D The comparison should be heap[index] < heap[parent]

💡 Hint

Check how parent index is calculated in a zero-based array heap.

In zero-based indexing, parent of node at index i is (i - 1) / 2. Using i / 2 is incorrect and causes wrong parent calculation.

🧠 Conceptual

advanced

How many swaps occur when inserting 50 into this max-heap?

Given the max-heap array [40, 30, 20, 15, 10, 5], how many swaps happen when inserting 50 and bubbling up?

A 0

B 1

C 3

D 2

💡 Hint

Count swaps as the inserted value moves up the tree comparing with parents.

Insert 50 at index 6. Parent at index 2 (20), swap 1. New index 2, parent at index 0 (40), swap 2. New index 0, no parent. Total 2 swaps.

❓ Predict Output

expert

What is the heap array after inserting 25 into this min-heap?

Given a min-heap array [5, 10, 15, 20, 30, 40], what is the array after inserting 25 and performing bubble up?

DSA C++

std::vector<int> heap = {5, 10, 15, 20, 30, 40};
int value = 25;
heap.push_back(value);
int i = heap.size() - 1;
while (i > 0) {
    int parent = (i - 1) / 2;
    if (heap[i] >= heap[parent]) break;
    std::swap(heap[i], heap[parent]);
    i = parent;
}
for (int v : heap) std::cout << v << " ";

A [5, 10, 15, 20, 30, 40, 25]

B [5, 10, 15, 20, 25, 40, 30]

C [5, 10, 15, 20, 30, 25, 40]

D [5, 10, 15, 20, 25, 30, 40]

💡 Hint

In a min-heap, bubble up swaps only if the child is smaller than the parent.

25 is inserted at the end. Its parent is 15, and since 25 > 15, no swaps occur. The heap remains [5, 10, 15, 20, 30, 40, 25].

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