Heap Concept Structure and Properties in DSA Javascript - 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 insert(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 a min-heap and moves it up to keep the heap property.

Identify Repeating Operations

Look for loops or repeated steps that happen as the heap changes.

• Primary operation: The while loop that moves the new value up the heap.
• How many times: At most, it moves up the height of the heap, which depends on the number of elements.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations (moves up)
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 is much smaller than the total elements.

Final Time Complexity

Time Complexity: O(log n)

This means adding an element takes time proportional to the heap's height, which grows slowly as the heap gets bigger.

Common Mistake

[X] Wrong: "Inserting into a heap takes the same time as scanning all elements, so it is O(n)."

[OK] Correct: The heap keeps elements in a tree shape, so we only move up the height, not through all elements.

Interview Connect

Knowing heap operations run in logarithmic time shows you understand efficient data structures, a key skill in many coding challenges.

Self-Check

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