Build Heap from Array Heapify in DSA Go - 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 work grows as the array size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

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 runs about n/2 times, and each heapify can recurse down the tree.

How Execution Grows With Input

Heapify work depends on the height of the tree at each node, which varies.

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 runs on n/2 nodes and each takes O(log n), so total is O(n log n)."

[OK] Correct: Most heapify calls are on nodes near the bottom with small height, so total work adds up to O(n), not O(n log n).

Interview Connect

Understanding this helps you explain why heap construction is efficient and prepares you for questions on priority queues and sorting.

Self-Check

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