Build Heap from Array Heapify in DSA Java

Mental Model

We turn an unordered list into a special tree where parents are bigger than children by fixing from the bottom up.

Analogy: Imagine stacking boxes so bigger boxes are always above smaller ones. You start fixing from the bottom boxes up to the top to keep the stack stable.

Array: [4, 10, 3, 5, 1]
Binary Tree:
       4
     /   \
   10     3
  /  \
 5    1

Dry Run Walkthrough

Input: array: [4, 10, 3, 5, 1]

Goal: Convert the array into a max heap where each parent is larger than its children

Step 1: Start heapify at index 1 (value 10), check children

[4, 10, 3, 5, 1]

Why: We start from the last parent node to fix subtree

Step 2: Heapify at index 1: children 5 and 1 are smaller, no change

[4, 10, 3, 5, 1]

Why: Subtree rooted at 10 already satisfies max heap

Step 3: Heapify at index 0 (value 4), children 10 and 3

[4, 10, 3, 5, 1]

Why: Check if root needs to swap with bigger child

Step 4: Swap 4 with 10 at index 1

[10, 4, 3, 5, 1]

Why: Parent must be bigger, so swap with bigger child

Step 5: Heapify at index 1 (value 4), children 5 and 1

[10, 4, 3, 5, 1]

Why: Fix subtree after swap

Step 6: Swap 4 with 5 at index 3

[10, 5, 3, 4, 1]

Why: 4 is smaller than child 5, swap to maintain heap

Step 7: Heapify at index 3 (value 4), no children

[10, 5, 3, 4, 1]

Why: Leaf node reached, heapify done

Result:

Final heap array: [10, 5, 3, 4, 1]

Annotated Code

DSA Java

public class BuildHeap {
    // Function to heapify subtree rooted at index i
    static void heapify(int[] arr, int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1; // left child index
        int right = 2 * i + 2; // right child index

        // If left child is larger than root
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected subtree
            heapify(arr, n, largest);
        }
    }

    // Function to build a max heap from array
    static void buildHeap(int[] arr) {
        int n = arr.length;
        // Start from last parent node and heapify each
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
    }

    // Driver code
    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        buildHeap(arr);
        // Print heap array
        for (int val : arr) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}

for (int i = n / 2 - 1; i >= 0; i--) {

start heapify from last parent node up to root

heapify(arr, n, i);

fix subtree rooted at i to satisfy max heap

if (left < n && arr[left] > arr[largest]) {

check if left child is bigger than current largest

if (right < n && arr[right] > arr[largest]) {

check if right child is bigger than current largest

if (largest != i) {

if root is not largest, swap and heapify affected subtree

Output

10 5 3 4 1 

Complexity Analysis

Time: O(n) because heapify is called on n/2 nodes and each call takes O(log n) worst but overall sums to O(n)

Space: O(1) because heapify works in place without extra arrays

vs Alternative: Naive approach inserting elements one by one into heap takes O(n log n), this bottom-up heapify is faster at O(n)

Edge Cases

empty array

buildHeap does nothing and array remains empty

DSA Java

for (int i = n / 2 - 1; i >= 0; i--) {

single element array

buildHeap does nothing and array remains unchanged

DSA Java

for (int i = n / 2 - 1; i >= 0; i--) {

all elements equal

heapify runs but no swaps happen, array unchanged

DSA Java

if (largest != i) {

When to Use This Pattern

When you need to quickly turn an unordered list into a heap for efficient priority operations, use build heap with bottom-up heapify to do it in linear time.

Common Mistakes

Mistake: Starting heapify from index 0 instead of last parent node
Fix: Start from n/2 - 1 down to 0 to ensure all subtrees are heapified

Mistake: Not recursively heapifying after swap
Fix: Call heapify recursively on the swapped child's index to fix subtree

Summary

Build Heap from Array Heapify converts an array into a max heap by fixing subtrees from bottom up.

Use it when you want to prepare an array for heap operations efficiently.

The key insight is starting heapify from the last parent node upwards to fix all subtrees.

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