Heap Concept Structure and Properties in DSA Typescript - Time & Space Complexity

Time Complexity: Heap Concept Structure and Properties

O(log n)

Understanding Time Complexity

We want to understand how the time to work with a heap changes as the heap grows.

Specifically, how fast can we add or remove items in a heap as it gets bigger?

Scenario Under Consideration

Analyze the time complexity of inserting an element into a heap.

function heapInsert(heap: number[], value: number): void {
  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 number to a max-heap and moves it up to keep the heap property.

Identify Repeating Operations

Look for loops or repeated steps that take time.

• Primary operation: The while loop that moves the new value up the heap.
• How many times: It runs until the new value reaches the top or finds a parent bigger than itself.

How Execution Grows With Input

As the heap grows, the height grows slowly compared to the number of items.

Input Size (n)	Approx. Operations (swaps)
10	About 3 or 4
100	About 6 or 7
1000	About 9 or 10

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 adding an item takes time proportional to the height of the heap, which grows slowly as the heap gets bigger.

Common Mistake

[X] Wrong: "Adding an item to a heap takes the same time no matter how big the heap is."

[OK] Correct: Because the new item may need to move up many levels, and the number of levels grows with the heap size.

Interview Connect

Understanding heap operations and their time costs shows you know how to handle priority data efficiently, a key skill in many coding challenges.

Self-Check

"What if we changed the heap to a min-heap? How would the time complexity of insertion change?"