Build Heap from Array Heapify in DSA Javascript - Time & Space Complexity

Time Complexity: Build Heap from Array Heapify

O(n)

Understanding Time Complexity

We want to understand how long it takes to build a heap from an unordered array using heapify.

How does the time needed grow as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function buildHeap(arr) {
  const n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
}

function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}
    

This code builds a max heap from an array by calling heapify on each non-leaf node starting from the bottom.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The heapify function called on each node from the bottom up.
• How many times: The for loop runs about n/2 times, and each heapify can recurse down the tree height.

How Execution Grows With Input

Heapify runs faster near the bottom because those nodes have smaller heights, and slower near the top with bigger heights.

Input Size (n)	Approx. Operations
10	About 20-30 operations
100	About 300-400 operations
1000	About 4000-5000 operations

Pattern observation: The total work grows a bit faster than linear but much slower than quadratic, closer to n log n.

Final Time Complexity

Time Complexity: O(n)

This means building a heap from an array takes time roughly proportional to the number of elements.

Common Mistake

[X] Wrong: "Heapify on each node takes O(log n), so building heap is O(n log n)."

[OK] Correct: Nodes near the bottom have smaller heights, so heapify is faster there. The total work adds up to O(n), not O(n log n).

Interview Connect

Understanding this time complexity shows you know how to analyze recursive and layered operations, a key skill for many coding challenges.

Self-Check

"What if we called heapify starting from the root down to the leaves instead? How would the time complexity change?"