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 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) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        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 on each non-leaf node.

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

How Execution Grows With Input

Heapify runs faster on nodes near the bottom because they have less height to move down.

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 linearly but much slower than n squared.

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 runs in O(log n) for each node, so buildHeap is O(n log n)."

[OK] Correct: Most nodes are near the bottom and heapify runs faster there, so total time adds up to O(n), not O(n log n).

Interview Connect

Knowing this time complexity helps you explain why heap construction is efficient and expected in many coding problems.

Self-Check

"What if we called heapify starting from the root only, repeatedly? How would the time complexity change?"

Practice

1. What is the main purpose of the heapify process when building a heap from an array?

easy

A. To find the maximum element in the array

B. To sort the array in ascending order

C. To reverse the array elements

D. To rearrange the array elements to satisfy the heap property

Solution

1. Step 1: Understand heap property

   A heap is a special tree where each parent node is greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role of heapify

   Heapify rearranges elements so the heap property holds for every subtree, starting from the bottom.

3. Final Answer:

   To rearrange the array elements to satisfy the heap property -> Option D

4. Quick Check:

   Heapify = Rearrange for heap property [OK]

Hint: Heapify fixes subtree order to build a heap fast [OK]

Common Mistakes:

• Thinking heapify sorts the array
• Confusing heapify with finding max/min element
• Assuming heapify reverses the array

2. Which of the following is the correct way to call heapify on an array arr of size n starting from index i in C?

easy

A. heapify(i, arr, n);

B. heapify(arr, n, i);

C. heapify(n, arr, i);

D. heapify(arr, i, n);

Solution

1. Step 1: Understand heapify parameters

   Heapify usually takes the array, its size, and the index to heapify from, in that order.

2. Step 2: Match correct syntax

   Calling heapify(arr, n, i); matches the standard parameter order: array, size, index.

3. Final Answer:

   heapify(arr, n, i); -> Option B

4. Quick Check:

   Function call order = arr, size, index [OK]

Hint: Remember: array first, then size, then index [OK]

Common Mistakes:

• Mixing parameter order
• Passing index before array
• Confusing size and index positions

3. Given the array arr = [4, 10, 3, 5, 1], what will be the array after calling heapify(arr, 5, 1) assuming a max-heap?

medium

A. [4, 5, 3, 10, 1]

B. [4, 1, 3, 5, 10]

C. [4, 10, 3, 5, 1]

D. [10, 4, 3, 5, 1]

Solution

1. Step 1: Identify children of index 1

   Index 1 has children at indices 3 and 4 with values 5 and 1.

2. Step 2: Compare and swap if needed

   Value at index 1 is 10, which is greater than both children, so no swap needed.

3. Final Answer:

   [4, 10, 3, 5, 1] -> Option C

4. Quick Check:

   Parent >= children, no change [OK]

Hint: Check parent vs children, swap only if smaller [OK]

Common Mistakes:

• Swapping when parent is already largest
• Mixing up child indices
• Assuming heapify sorts entire array

4. Consider this code snippet to build a max heap from array arr of size n. Identify the error:

for (int i = 0; i <= n/2; i++) {
    heapify(arr, n, i);
}

medium

A. Loop should start from n/2 - 1 and go down to 0

B. Loop should start from 0 and go to n - 1

C. heapify function parameters are incorrect

D. No error, code is correct

Solution

1. Step 1: Understand heap building order

   Heap building starts from last non-leaf node at index n/2 - 1 down to 0.

2. Step 2: Check loop direction and range

   Loop incorrectly goes up from 0 to n/2, should go down from n/2 - 1 to 0.

3. Final Answer:

   Loop should start from n/2 - 1 and go down to 0 -> Option A

4. Quick Check:

   Build heap loops down from n/2-1 [OK]

Hint: Build heap loops backward from last parent [OK]

Common Mistakes:

• Looping forward instead of backward
• Starting loop at 0 without going down
• Incorrect heapify parameters

5. You have the array [3, 9, 2, 1, 4, 5]. After building a max heap using heapify from the bottom up, what is the final array?

hard

A. [9, 4, 5, 1, 3, 2]

B. [9, 5, 4, 1, 3, 2]

C. [9, 3, 5, 1, 4, 2]

D. [9, 4, 5, 3, 1, 2]

Solution

1. Step 1: Start heapify from last non-leaf node

   Last non-leaf node index = n/2 - 1 = 2. Heapify at index 2: children 5 and no right child. Swap 2 and 5 -> [3,9,5,1,4,2]

2. Step 2: Heapify at index 1

   Index 1 value 9, children 1 and 4. 9 is largest, no swap -> [3,9,5,1,4,2]

3. Step 3: Heapify at index 0

   Index 0 value 3, children 9 and 5. Largest is 9 at index 1, swap -> [9,3,5,1,4,2]. Heapify at index 1 again: 3 with children 1 and 4, largest is 4 at index 4, swap -> [9,4,5,1,3,2]

4. Final Answer:

   [9, 4, 5, 1, 3, 2] -> Option A

5. Quick Check:

   Bottom-up heapify fixes subtree order [OK]

Hint: Heapify bottom-up swaps parents with largest child [OK]

Common Mistakes:

• Not heapifying children after swap
• Swapping with wrong child
• Stopping heapify too early