Build Heap from Array Heapify in DSA C

Mental Model

We turn an unordered array into a heap by fixing each subtree from bottom up, ensuring the heap property holds everywhere.

Analogy: Imagine organizing a messy pile of books into neat stacks by starting from the bottom shelves and fixing each stack so the biggest book is always on top.

Array: [4, 10, 3, 5, 1]
Heap 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 greater than its children

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

[4, 10, 3, 5, 1]

Why: We start from the last non-leaf node to fix subtrees bottom-up

Step 2: Index 1 is already larger than children, no swap needed

[4, 10, 3, 5, 1]

Why: Heap property holds at this subtree

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

[4, 10, 3, 5, 1]

Why: Fix root subtree to maintain heap property

Step 4: Swap 4 with largest child 10

[10, 4, 3, 5, 1]

Why: Parent must be larger than children

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

[10, 4, 3, 5, 1]

Why: After swap, fix subtree rooted at index 1

Step 6: Swap 4 with largest child 5

[10, 5, 3, 4, 1]

Why: Maintain heap property in subtree

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

[10, 5, 3, 4, 1]

Why: Leaf node reached, no further action

Result:

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

Annotated Code

DSA C

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

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 < n && arr[left] > arr[largest])
        largest = left; // left child is larger

    if (right < n && arr[right] > arr[largest])
        largest = right; // right child is larger

    if (largest != i) {
        swap(&arr[i], &arr[largest]); // swap root with largest child
        heapify(arr, n, largest); // recursively heapify affected subtree
    }
}

void buildHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i); // heapify from last non-leaf to root
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i != n - 1) printf(", ");
    }
    printf("\n");
}

int main() {
    int arr[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    buildHeap(arr, n);
    printArray(arr, n);

    return 0;
}

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

Check if left child is larger than current largest

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

Check if right child is larger than current largest

if (largest != i) { swap(&arr[i], &arr[largest]); heapify(arr, n, largest); }

Swap root with largest child and heapify subtree recursively

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

Build heap by heapifying all non-leaf nodes bottom-up

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 build heap is O(n) due to decreasing subtree sizes

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

vs Alternative: Naive approach inserting elements one by one into heap is O(n log n), so build heap is more efficient

Edge Cases

Empty array

No heapify calls, array remains empty

DSA C

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

Single element array

Heapify called once but no swaps needed

DSA C

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

All elements equal

No swaps happen, heap property already holds

DSA C

if (largest != i) {

When to Use This Pattern

When you need to quickly turn an unordered array into a heap for efficient priority operations, use build heap with bottom-up heapify to achieve O(n) time.

Common Mistakes

Mistake: Starting heapify from index 0 instead of last non-leaf node
Fix: Start from n/2 - 1 down to 0 to ensure all subtrees are fixed bottom-up

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 rearranges an array into a heap by fixing subtrees from bottom up.

Use it when you want to create a heap efficiently from an unordered array.

The key insight is starting heapify from the last non-leaf node and moving upward ensures all subtrees satisfy heap property.

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