Build Heap from Array Heapify in DSA Typescript - 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 array using heapify.

Specifically, how the time grows as the array size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

function heapify(arr: number[], n: number, i: number): void {
  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 unsorted array by calling heapify from the bottom up.

Identify Repeating Operations

• Primary operation: The heapify function called on each non-leaf node.
• How many times: Called once for each node from the middle to the root, about n/2 times.
• Inside heapify: It may recurse down the tree, moving elements to maintain heap property.

How Execution Grows With Input

Heapify runs faster on nodes near the bottom because they have fewer levels to move down.

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

Pattern observation: The total work grows roughly linearly with input size, not quadratically.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Heapify runs in O(n log n) because heapify is called n/2 times and each call takes O(log n)."

[OK] Correct: Most heapify calls run on nodes near the bottom with small heights, so they take less time. The total adds up to O(n), not O(n log n).

Interview Connect

Understanding this helps you explain why heap construction is efficient and shows you can analyze recursive code carefully.

Self-Check

What if we called heapify starting from the root down to the last node instead of bottom-up? How would the time complexity change?