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

Time Complexity: Heap Insert Operation 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 involves moving the new item up the heap if it's bigger or smaller than its parent.

We want to know how the time to do this moving up changes as the heap grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function bubbleUp(heap: number[], index: number): void {
  while (index > 0) {
    const parentIndex = Math.floor((index - 1) / 2);
    if (heap[index] <= heap[parentIndex]) break;
    [heap[index], heap[parentIndex]] = [heap[parentIndex], heap[index]];
    index = parentIndex;
  }
}
    

This code moves the newly added element up the heap 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 element with its parent.
• How many times: At most, this loop runs once per level of the heap, moving from the inserted node up to the root.

How Execution Grows With Input

Each time we add a new item, it might move up several levels. The heap is a tree with levels growing slowly as the heap grows.

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

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

Final Time Complexity

Time Complexity: O(log n)

This means the time to insert and bubble up grows slowly as the heap gets bigger, only increasing with the height of the heap.

Common Mistake

[X] Wrong: "The bubble up always takes as long as the number of items in the heap (O(n))."

[OK] Correct: The heap is a balanced tree, so the bubble up only moves up the height of the tree, which grows much slower than the total number of items.

Interview Connect

Understanding how bubble up works and its time cost helps you explain heap insertions clearly and confidently, a skill often valued in interviews.

Self-Check

What if we changed the heap to a linked structure instead of an array? How would the time complexity of bubble up change?