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

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

private 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);
    }
}
    

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: Called once for each node from n/2 - 1 down to 0, so about n/2 times.
• Inside heapify: It may recurse down the tree, doing work proportional to the height of the subtree.

How Execution Grows With Input

Heapify work depends on node height; nodes near bottom have small height, fewer calls.

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 n, 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 are on nodes near the bottom with small height, so their work is much less than log n. Summing all work over all nodes results in O(n), not O(n log n).

Interview Connect

Understanding this time complexity shows you know how to analyze recursive work and why some algorithms are faster than they seem.

Self-Check

"What if we built the heap by inserting elements one by one instead of heapifying the whole array? 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 rearrange the array elements to satisfy the heap property

B. To sort the array in ascending order

C. To find the maximum element in the array

D. To reverse the array elements

Solution

1. Step 1: Understand heap property

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

2. Step 2: Role of heapify

   The heapify process rearranges elements so that the heap property is maintained starting from a node down to its children.

3. Final Answer:

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

4. Quick Check:

   Heapify = Rearrange for heap property [OK]

Hint: Heapify fixes heap property from a node down [OK]

Common Mistakes:

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

2. Which of the following is the correct way to start heapifying an array of size n in Java when building a max heap?

easy

A. for (int i = 0; i < n; i++) heapify(arr, i, n);

B. for (int i = n - 1; i >= 0; i--) heapify(arr, i, n);

C. for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, i, n);

D. for (int i = 1; i < n; i++) heapify(arr, i, n);

Solution

1. Step 1: Identify heapify start index

   Heapify starts from the last non-leaf node, which is at index n/2 - 1, moving upwards to root.

2. Step 2: Loop direction and range

   The loop runs backward from n/2 - 1 down to 0 to ensure all subtrees satisfy heap property.

3. Final Answer:

   for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, i, n); -> Option C

4. Quick Check:

   Start heapify at last non-leaf node [OK]

Hint: Start heapify from n/2 - 1 down to 0 [OK]

Common Mistakes:

• Starting heapify from index 0 upwards
• Heapifying leaf nodes unnecessarily
• Looping in wrong direction

3. Given the array [4, 10, 3, 5, 1], what will be the array after building a max heap using heapify?

medium

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

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

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

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

Solution

1. Step 1: Start heapify from index 1 (n/2 - 1)

   Heapify at index 1: children are 5 and 1. Max child is 5. Swap 10 and 5? No, 10 > 5, so no swap.

2. Step 2: Heapify at index 0

   At index 0: value 4, children 10 and 3. Max child is 10. Swap 4 and 10. Array becomes [10, 4, 3, 5, 1]. Now heapify at index 1 again.

3. Step 3: Heapify at index 1 again

   At index 1: value 4, children 5 and 1. Max child is 5. Swap 4 and 5. Array becomes [10, 5, 3, 4, 1].

4. Final Answer:

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

5. Quick Check:

   Max heap built correctly [OK]

Hint: Heapify bottom-up swaps to fix max heap [OK]

Common Mistakes:

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

4. Consider this heapify method snippet in Java:

void heapify(int[] arr, int i, int n) {
  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, largest, n);
  }
}

What is the bug if the method is called with heapify(arr, 0, arr.length - 1)?

medium

A. The size parameter should be arr.length, not arr.length - 1

B. The left and right child calculations are incorrect

C. The recursive call should be heapify(arr, i, n) instead of heapify(arr, largest, n)

D. The swap logic is missing

Solution

1. Step 1: Understand parameter n meaning

   Parameter n represents the size of the array segment to heapify, so it should be the length of the array.

2. Step 2: Identify off-by-one error

   Using arr.length - 1 excludes the last element, causing incorrect heapify behavior and possible index errors.

3. Final Answer:

   The size parameter should be arr.length, not arr.length - 1 -> Option A

4. Quick Check:

   Pass full length for heapify size [OK]

Hint: Pass full array length, not length minus one [OK]

Common Mistakes:

• Passing length - 1 as size
• Miscalculating child indices
• Incorrect recursive call parameters

5. You have an array [3, 9, 2, 1, 4, 5]. After building a max heap using heapify, what will be the array? Also, explain why starting heapify from n/2 - 1 is efficient compared to starting from index 0.

hard

A. [9, 5, 4, 3, 2, 1]; starting from 0 is better for full coverage

B. [9, 4, 5, 1, 3, 2]; starting from n/2 - 1 avoids unnecessary heapify on leaf nodes

C. [5, 9, 4, 3, 2, 1]; starting from n/2 - 1 is inefficient

D. [3, 9, 2, 1, 4, 5]; heapify does not change array order

Solution

1. Step 1: Build max heap from bottom up

   Start heapify at index 2 (n/2 - 1 = 6/2 - 1 = 2): - At index 2 (value 2), children: 5 (index 5), no right child. - Swap 2 and 5 -> [3, 9, 5, 1, 4, 2] Heapify at index 1: - Value 9, children 1 and 4, no swap. Heapify at index 0: - Value 3, children 9 and 5. - Swap 3 and 9 -> [9, 3, 5, 1, 4, 2] Heapify at index 1: - Value 3, children 1 and 4. - Swap 3 and 4 -> [9, 4, 5, 1, 3, 2]

2. Step 2: Explain efficiency of starting at n/2 - 1

   Nodes from n/2 to n-1 are leaf nodes with no children, so heapify on them is unnecessary. Starting at n/2 - 1 reduces calls and improves efficiency.

3. Final Answer:

   [9, 4, 5, 1, 3, 2]; starting from n/2 - 1 avoids unnecessary heapify on leaf nodes -> Option B

4. Quick Check:

   Heapify bottom-up skips leaves for efficiency [OK]

Hint: Heapify from last non-leaf node skips leaves [OK]

Common Mistakes:

• Heapifying leaf nodes unnecessarily
• Incorrect swaps during heapify
• Misunderstanding heapify start index