Build Heap from Array Heapify in DSA C++ - 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 unsorted 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.

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int 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) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void buildHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

This code builds a max heap from an unsorted array by calling heapify from the bottom non-leaf nodes up to the root.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The heapify function called on each non-leaf node.
• How many times: The for loop calls heapify about n/2 times, once for each non-leaf node.
• Each heapify call may recurse down the tree, but the depth depends on the node's height.

How Execution Grows With Input

Heapify work depends on node height; nodes near bottom do less work, nodes near top do more.

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 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 is called n/2 times and each call can take up to log n, so total time is O(n log n)."

[OK] Correct: Most heapify calls happen on nodes near the bottom with small height, so they do less work. The total sums up to O(n), not O(n log n).

Interview Connect

Knowing that building a heap is O(n) helps you explain efficient data structure setup in interviews confidently.

Self-Check

"What if we used a different method that inserts elements one by one into an empty heap? How would the time complexity change?"