Heap Insert Operation Bubble Up in DSA C++ - Time & Space Complexity

Time Complexity: Heap Insert Operation Bubble Up

O(log n)

Understanding Time Complexity

We want to understand how long it takes to add a new item to a heap and fix its position.

How does the time needed grow as the heap gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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;
  }
}
    

This code moves the newly inserted element up the heap until the heap property is restored.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing and swapping the inserted element with its parent.
• How many times: At most once per level up the heap, from the inserted node to the root.

How Execution Grows With Input

Each step moves the element one level up the heap tree, which has a height related to the number of elements.

Input Size (n)	Approx. Operations
10	About 4 steps (levels)
100	About 7 steps
1000	About 10 steps

Pattern observation: The number of steps grows slowly, roughly with the height of the heap, which increases as the logarithm of n.

Final Time Complexity

Time Complexity: O(log n)

This means the time to fix the heap after insertion grows slowly as the heap gets bigger, only about one step per level.

Common Mistake

[X] Wrong: "The insert operation takes constant time because we just add at the end."

[OK] Correct: Adding at the end is quick, but fixing the heap order by moving the element up can take multiple steps depending on heap height.

Interview Connect

Knowing this time complexity helps you explain why heaps are efficient for priority queues and sorting, showing you understand how data structure operations scale.

Self-Check

"What if the heap was a ternary heap (each node has 3 children) instead of binary? How would the time complexity change?"

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