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.