Build Heap from Array Heapify in DSA C++

Mental Model

We turn an unordered list into a heap by fixing each parent node from the bottom up so the heap property holds everywhere.

Analogy: Imagine stacking boxes in a pyramid where each box must be larger than the boxes below it. We start fixing from the bottom rows up to the top to make the pyramid stable.

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

Array: [4, 10, 3, 5, 1]

Why: We start from the last parent node to fix heap property bottom-up

Step 2: No swap needed since 10 is greater than children 5 and 1

Array: [4, 10, 3, 5, 1]

Why: Parent 10 already satisfies heap property

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

Array: [4, 10, 3, 5, 1]

Why: Fix heap property at root by comparing with children

Step 4: Swap 4 with largest child 10

Array: [10, 4, 3, 5, 1]

Why: Parent must be larger than children, so swap with largest child

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

Array: [10, 4, 3, 5, 1]

Why: After swap, fix subtree rooted at index 1

Step 6: Swap 4 with largest child 5

Array: [10, 5, 3, 4, 1]

Why: Maintain heap property by swapping with largest child

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

Array: [10, 5, 3, 4, 1]

Why: Leaf node reached, no further action

Result:

Array: [10, 5, 3, 4, 1]
Heap tree:
        10
      /    \
     5      3
    /  \
   4    1

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void heapify(vector<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) {
        swap(arr[i], arr[largest]); // swap root with largest child
        heapify(arr, n, largest); // recursively heapify the affected subtree
    }
}

void buildHeap(vector<int>& arr) {
    int n = arr.size();
    // Start from last parent node and heapify each
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

void printHeap(const vector<int>& arr) {
    for (int val : arr) {
        cout << val << " ";
    }
    cout << "\n";
}

int main() {
    vector<int> arr = {4, 10, 3, 5, 1};
    buildHeap(arr);
    printHeap(arr);
    return 0;
}

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

compare left child with current largest to find max

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

compare right child with current largest to find max

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

swap parent with largest child and recursively fix subtree

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

build heap by heapifying all parents from 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) in worst case but overall sums to O(n)

Space: O(log n) due to recursion stack in heapify calls

vs Alternative: Naive approach inserting elements one by one into heap is O(n log n), so this bottom-up heapify is more efficient

Edge Cases

empty array

buildHeap does nothing and array remains empty

DSA C++

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

array with one element

heapify runs once but no swaps needed, array unchanged

DSA C++

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

array with all equal elements

no swaps happen, heap property already holds

DSA C++

if (largest != i)

When to Use This Pattern

When you need to convert an unordered array into a heap efficiently, use bottom-up heapify starting from last parent to root to build the heap in O(n) time.

Common Mistakes

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

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

Summary

Builds a max heap from an unordered array by fixing heap property bottom-up.

Use when you want to efficiently create a heap from existing data.

Start heapify from last parent node and fix subtrees recursively to ensure 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 rearrange elements to satisfy the heap property

D. To reverse the array elements

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 this property holds for every subtree starting from a node.

3. Final Answer:

   To rearrange elements to satisfy the heap property -> Option C

4. Quick Check:

   Heapify = rearrange for heap property [OK]

Hint: Heapify fixes subtree to maintain heap order fast [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 call heapify on an array arr of size n starting from index i in C++?

easy

A. heapify(i, arr, n);

B. heapify(arr, i, n);

C. heapify(n, i, arr);

D. heapify(arr, n, i);

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

   heapify(arr, n, i); matches the standard signature: heapify(arr, n, i); others have wrong order.

3. Final Answer:

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

4. Quick Check:

   heapify(arr, size, index) = B [OK]

Hint: Remember: array, size, then index for heapify call [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, 0) assuming a max-heap?

medium

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

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

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

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

Solution

1. Step 1: Identify root and children

   Index 0 has value 4; children at indices 1 and 2 are 10 and 3.

2. Step 2: Swap with largest child and heapify

   Swap 4 with 10 (largest child). Now at index 1, value 4 has children 5 and 1. Swap 4 with 5. Final array: [10, 5, 3, 4, 1]

3. Final Answer:

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

4. Quick Check:

   Max-heap root fixed = [10, 5, 3, 4, 1] [OK]

Hint: Swap root with largest child, then heapify child subtree [OK]

Common Mistakes:

• Not swapping with largest child
• Stopping after first swap
• Confusing min-heap with max-heap

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. Heapify should be called with index i+1

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

C. Loop should run from 0 to n-1

D. No error, code is correct

Solution

1. Step 1: Understand heap building order

   Heap building requires heapify from last non-leaf node down to root, i.e., from n/2 - 1 down to 0.

2. Step 2: Identify loop direction and range error

   The loop incorrectly goes from 0 up to n/2, which is wrong direction and range.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Looping forward instead of backward
• Starting loop at 0 without decrement
• Calling heapify with wrong index

5. You have an array arr = [3, 9, 2, 1, 4, 5]. After building a max heap using the standard heapify method, what is the final array?

hard

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

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

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

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

Solution

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

   Last non-leaf index = n/2 -1 = 2. Heapify at index 2: children 5 and none, 2 < 5, swap to get [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 change.

3. Step 3: Heapify at index 0

   Index 0 value 3, children 9 and 5. Swap 3 with 9: [9,3,5,1,4,2]. Heapify at index 1: value 3, children 1 and 4. Swap 3 with 4: [9,4,5,1,3,2].

4. Final Answer:

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

5. Quick Check:

   Max heap built = [9,4,5,1,3,2] [OK]

Hint: Heapify bottom-up, swap with largest child repeatedly [OK]

Common Mistakes:

• Not heapifying all parents
• Swapping with wrong child
• Stopping heapify early