Heap insertion (bubble up) in Data Structures Theory - Time & Space Complexity

Time Complexity: Heap insertion (bubble up)

O(log n)

Understanding Time Complexity

When we add a new item to a heap, we need to keep the heap rules intact. This process is called "bubble up."

We want to know how the time to do this grows as the heap gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function heapInsert(heap, value) {
  heap.push(value);
  let index = heap.length - 1;
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2);
    if (heap[parentIndex] >= heap[index]) break;
    [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]];
    index = parentIndex;
  }
}
    

This code adds a new value to the heap and moves it up until the heap property is restored.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that compares and swaps the new value with its parent.
• How many times: At most, this loop runs once per level of the heap, moving up from the inserted node to the root.

How Execution Grows With Input

Each time we add a new item, it might move up several levels. The number of levels grows slowly as the heap grows.

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 heap size grows.

Final Time Complexity

Time Complexity: O(log n)

This means the time to insert grows slowly, proportional to the height of the heap, not the total number of items.

Common Mistake

[X] Wrong: "Insertion takes the same time no matter how big the heap is because we just add at the end."

[OK] Correct: While adding at the end is quick, restoring the heap order by moving the new item up can take more steps as the heap grows.

Interview Connect

Understanding heap insertion time helps you explain how priority queues work efficiently. It shows you can analyze how data structure operations scale with size.

Self-Check

"What if the heap was a min-heap instead of a max-heap? How would the time complexity of insertion change?"

Practice

1. What is the first step when inserting a new element into a binary heap using the bubble up method?

easy

A. Add the new element at the end of the heap

B. Compare the new element with the root

C. Remove the smallest element

D. Sort all elements in the heap

Solution

1. Step 1: Add new element at the end

   The new element is always added at the end of the heap to maintain the complete tree property.

2. Step 2: Prepare for bubble up

   After adding, the element will be compared with its parent to restore heap order.

3. Final Answer:

   Add the new element at the end of the heap -> Option A

4. Quick Check:

   Insertion starts by adding at the end [OK]

Hint: New elements always start at the end before bubbling up [OK]

Common Mistakes:

• Starting at the root instead of the end
• Removing elements before insertion
• Sorting the entire heap immediately

2. Which of the following correctly describes the condition to continue bubbling up in a min-heap after insertion?

easy

A. Never bubble up after insertion

B. Continue bubbling up if the new element is greater than its parent

C. Continue bubbling up if the new element is equal to its parent

D. Continue bubbling up if the new element is less than its parent

Solution

1. Step 1: Understand min-heap property

   In a min-heap, parents must be less than or equal to their children.

2. Step 2: Bubble up condition

   If the new element is less than its parent, it violates the heap property and must bubble up.

3. Final Answer:

   Continue bubbling up if the new element is less than its parent -> Option D

4. Quick Check:

   Bubble up when child < parent in min-heap [OK]

Hint: Bubble up when new element is smaller than parent in min-heap [OK]

Common Mistakes:

• Bubbling up when new element is greater
• Ignoring equality cases
• Not bubbling up at all

3. Given a min-heap represented as an array: [2, 5, 8, 10, 15], what will be the array 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

   Array becomes [2, 5, 8, 10, 15, 1].

2. Step 2: Bubble up 1

   Compare 1 with parent 8 (index 2). Since 1 < 8, swap: [2, 5, 1, 10, 15, 8]. Then compare 1 with parent 5 (index 1). Since 1 < 5, swap: [2, 1, 8, 10, 15, 5]. Then compare 1 with parent 2 (index 0). Since 1 < 2, swap: [1, 2, 8, 10, 15, 5].

3. Final Answer:

   [1, 2, 5, 10, 15, 8] -> 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 enough times
• Swapping with wrong parent
• Leaving new element at the end

4. Consider the following code snippet for inserting into a min-heap. What is the error?

def bubble_up(heap, index):
    while index > 0:
        parent = (index - 1) // 2
        if heap[index] > heap[parent]:
            heap[index], heap[parent] = heap[parent], heap[index]
            index = parent
        else:
            break

medium

A. The comparison should be heap[index] < heap[parent] for min-heap

B. The parent index calculation is incorrect

C. The loop condition should be index >= 0

D. Swapping should happen only if heap[index] == heap[parent]

Solution

1. Step 1: Analyze comparison logic

   For a min-heap, bubble up should swap when child is less than parent, not greater.

2. Step 2: Identify correct condition

   The code uses '>' which is wrong; it should be '<' to maintain min-heap property.

3. Final Answer:

   The comparison should be heap[index] < heap[parent] for min-heap -> Option A

4. Quick Check:

   Bubble up swaps when child < parent in min-heap [OK]

Hint: Use < comparison for min-heap bubble up [OK]

Common Mistakes:

• Using > instead of <
• Wrong parent index formula
• Incorrect loop condition

5. You have a max-heap represented as [20, 15, 18, 8, 10, 17]. You insert 19. After bubble up, what is the correct heap array?

hard

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

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

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

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

Solution

1. Step 1: Insert 19 at the end

   Array becomes [20, 15, 18, 8, 10, 17, 19].

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

   Parent of index 6 is index 2 (value 18). Since 19 > 18, swap: [20, 15, 19, 8, 10, 17, 18]. Next parent is index 0 (value 20). Since 19 < 20, stop bubbling up.

3. Step 3: Final heap array

   The final array is [20, 15, 19, 8, 10, 17, 18].

4. Final Answer:

   [20, 15, 19, 8, 10, 17, 18] -> Option C

5. Quick Check:

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

Hint: In max-heap, bubble up while child is greater than parent [OK]

Common Mistakes:

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