Why Heap Exists and What Sorted Array Cannot Do Efficiently in DSA Javascript - Performance Analysis

Time Complexity: Why Heap Exists and What Sorted Array Cannot Do Efficiently

O(n)

Understanding Time Complexity

We want to understand why heaps are useful compared to sorted arrays.

Specifically, what tasks are slow with sorted arrays but faster with heaps?

Scenario Under Consideration

Analyze the time complexity of these two operations on a sorted array:

// Remove the smallest element (first element)
function removeMin(sortedArray) {
  return sortedArray.shift(); // removes first element
}

// Insert a new element while keeping array sorted
function insertSorted(sortedArray, value) {
  let i = 0;
  while (i < sortedArray.length && sortedArray[i] < value) {
    i++;
  }
  sortedArray.splice(i, 0, value);
}
    

This code removes the smallest item and inserts a new item keeping the array sorted.

Identify Repeating Operations

Look at the loops and array operations that repeat:

• Primary operation: Loop to find insert position and shifting elements on insert and remove.
• How many times: Up to n times, where n is the array size.

How Execution Grows With Input

As the array grows, these operations take longer:

Input Size (n)	Approx. Operations
10	About 10 steps to insert or remove
100	About 100 steps to insert or remove
1000	About 1000 steps to insert or remove

Pattern observation: The time grows roughly in direct proportion to the size of the array.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert or remove grows linearly as the array gets bigger.

Common Mistake

[X] Wrong: "Since the array is sorted, insertion and removal must be very fast, like O(1)."

[OK] Correct: Even though the array is sorted, inserting or removing at the start requires shifting many elements, which takes time proportional to the array size.

Interview Connect

Understanding these time costs helps you explain why heaps are used to get faster insert and remove operations compared to sorted arrays.

Self-Check

"What if we used a heap instead of a sorted array? How would the time complexity for insert and remove change?"