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

Practice

1. Why do we use a heap instead of just a sorted array when we want to repeatedly access the smallest element?

easy

A. Because heaps allow faster insertion and deletion of the smallest element than sorted arrays.

B. Because heaps store elements in sorted order all the time.

C. Because sorted arrays use less memory than heaps.

D. Because heaps are easier to implement than sorted arrays.

Solution

1. Step 1: Understand operations on sorted arrays

   Inserting or deleting elements in a sorted array requires shifting elements, which takes linear time (O(n)).

2. Step 2: Compare with heap operations

   Heaps allow insertion and deletion of the smallest element in logarithmic time (O(log n)) by maintaining a special tree structure.

3. Final Answer:

   Because heaps allow faster insertion and deletion of the smallest element than sorted arrays. -> Option A

4. Quick Check:

   Heap operations faster than sorted array for insert/delete [OK]

Hint: Heaps speed up insert/delete of min element vs sorted arrays [OK]

Common Mistakes:

• Thinking heaps keep all elements fully sorted
• Assuming sorted arrays have faster insertions
• Confusing memory usage with operation speed

2. Which of the following is the correct way to insert an element into a min-heap represented as an array in JavaScript?

easy

A. Replace the root with the new element and heapify down.

B. Insert element at the start and sort the array.

C. Add element at the end and do nothing else.

D. Add element at the end, then bubble it up to maintain heap property.

Solution

1. Step 1: Recall min-heap insertion process

   Insert the new element at the end of the array to keep the complete tree shape.

2. Step 2: Restore heap property by bubbling up

   Compare the new element with its parent and swap if smaller, repeat until heap property is restored.

3. Final Answer:

   Add element at the end, then bubble it up to maintain heap property. -> Option D

4. Quick Check:

   Insert by adding end + bubble up [OK]

Hint: Insert at end, then bubble up to fix heap [OK]

Common Mistakes:

• Sorting the whole array after insertion
• Not bubbling up after insertion
• Replacing root directly without insertion

3. Consider this JavaScript code using a min-heap array representation:

const heap = [2, 5, 3, 10, 7];
// Insert 1 into heap
heap.push(1);
// Bubble up process
let i = heap.length - 1;
while (i > 0) {
  let parent = Math.floor((i - 1) / 2);
  if (heap[i] < heap[parent]) {
    [heap[i], heap[parent]] = [heap[parent], heap[i]];
    i = parent;
  } else {
    break;
  }
}
console.log(heap);

What is the output after insertion and bubbling up?

medium

A. [1, 2, 3, 10, 7, 5]

B. [1, 5, 3, 10, 7, 2]

C. [1, 5, 2, 10, 7, 3]

D. [1, 3, 2, 10, 7, 5]

Solution

1. Step 1: Insert 1 at the end

   Initial heap: [2, 5, 3, 10, 7] After push: [2, 5, 3, 10, 7, 1]

2. Step 2: Bubble up 1 to restore heap

   Index i=5, parent = 2 heap[5]=1 < heap[2]=3, swap -> [2, 5, 1, 10, 7, 3] Now i=2, parent=0 heap[2]=1 < heap[0]=2, swap -> [1, 5, 2, 10, 7, 3] Now i=0, stop.

3. Final Answer:

   [1, 5, 2, 10, 7, 3] -> Option C

4. Quick Check:

   Bubble up swaps 1 up to root [OK]

Hint: Bubble up swaps until parent smaller or root reached [OK]

Common Mistakes:

• Swapping with wrong parent index
• Stopping bubble up too early
• Incorrect array after swaps

4. The following code tries to remove the smallest element from a min-heap represented as an array. What is the bug?

function removeMin(heap) {
  if (heap.length === 0) return null;
  const min = heap[0];
  heap[0] = heap.pop();
  let i = 0;
  while (true) {
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let smallest = i;
    if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
    if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
    if (smallest === i) break;
    [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
    i = smallest;
  }
  return min;
}

medium

A. It does not handle the case when heap has only one element.

B. It does not handle empty heap correctly.

C. It does not check if heap.pop() returns undefined.

D. It does not update the index i correctly after swapping.

Solution

1. Step 1: Analyze removal when heap has one element

   If heap has one element, heap.pop() removes it, then heap[0] = undefined sets root to undefined, causing invalid heap state.

2. Step 2: Check code for single element case

   Code does not handle this special case; it should return the popped element directly without reassigning heap[0].

3. Final Answer:

   It does not handle the case when heap has only one element. -> Option A

4. Quick Check:

   Single element removal needs special handling [OK]

Hint: Check single-element heap removal edge case [OK]

Common Mistakes:

• Ignoring single-element heap case
• Assuming pop always returns a value
• Not updating index after swap (actually correct here)

5. You want to maintain a collection of numbers where you frequently insert new numbers and also frequently remove the smallest number. Why is a heap better than a sorted array for this use case, and what is the time complexity difference?

hard

A. Heap allows insert and remove-min in O(log n), while sorted array requires O(n) for insert and O(1) for remove-min.

B. Heap allows insert and remove-min in O(log n), while sorted array requires O(n) for both insert and remove-min.

C. Heap allows insert and remove-min in O(1), while sorted array requires O(n) for insert and remove-min.

D. Heap allows insert and remove-min in O(n), while sorted array requires O(log n) for insert and remove-min.

Solution

1. Step 1: Analyze heap operation times

   Insertion and removal of smallest element in a heap both take O(log n) time due to bubbling up/down.

2. Step 2: Analyze sorted array operation times

   Insertion requires shifting elements to keep sorted order, O(n). Removing smallest (first element) requires shifting all remaining elements left, O(n).

3. Final Answer:

   Heap allows insert and remove-min in O(log n), while sorted array requires O(n) for both insert and remove-min. -> Option B

4. Quick Check:

   Heap: O(log n) insert/remove, Sorted array: O(n) insert/remove [OK]

Hint: Heap: O(log n) insert/remove; sorted array O(n) both [OK]

Common Mistakes:

• Thinking sorted array remove-min is O(1)
• Assuming heap insert/remove is O(1)
• Confusing insert and remove complexities