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?"