Build a Heap (Heapify)

So you have a plain array of numbers in any random order. You want to turn it into a heap. A heap is a tree-shaped arrangement where every parent is bigger than its children, stored inside an array. The question is how do you do that fast?

You could pick numbers one by one and insert them into a fresh heap. That works, but it is slow. There is a smarter way called heapify. It fixes the whole array in one bottom-up pass. Let us see how.

🎯 What “Build a Heap” Means

Building a heap means taking an unordered array and rearranging its values so it follows the heap rule.

In a max heap, every parent node is greater than or equal to its children. The biggest value ends up at the root.

The array itself does not change size. We just swap values around until the order is correct. Remember the index math for an array-based heap:

• the left child of index i sits at 2*i + 1
• the right child of index i sits at 2*i + 2
• the parent of index i sits at (i - 1) / 2

So we never build an actual tree with pointers. The array is the tree.

🧠 The Slow Way vs The Clever Way

The simple idea is to insert each number one at a time into a growing heap. Every insert may travel up the tree to fix the order. That costs O(log n). Do it for n numbers and you get O(n log n).

The clever way is heapify. Instead of going top-down with inserts, we go bottom-up and fix small heaps first.

Here is the key idea in plain words:

• Leaf nodes have no children. So they are already tiny valid heaps on their own.
• That means we can skip all the leaves and start from the last node that actually has a child.
• For each such node we push it down to its correct spot. This is called sift-down.
• We move backwards toward the root. We fix bigger and bigger sub-heaps as we go.

🔧 What Is Sift-Down?

Sift-down takes one node that might be out of place and pushes it down until the heap rule holds.

The steps for sift-down on index i:

• Look at node i and its two children.
• Find the largest among the parent and its children.
• If the parent is already the largest, stop. Nothing to do.
• Otherwise swap the parent with the largest child.
• Now the problem moved down. So repeat sift-down at that child’s index.

⚡ Why Bottom-Up Heapify Is O(n)

This part surprises a lot of people. We run sift-down on roughly half the nodes. Each sift-down can cost up to O(log n). So you would guess O(n log n). But the real cost is O(n). Here is the simple reason.

The cost of sift-down depends on the node’s height, not the tree’s height. A node near the bottom can only fall a tiny distance.

• Most nodes live near the bottom of the tree. They have height 0 or 1, so their sift-down is almost free.
• Only a few nodes live near the top. They can fall far, but there are very few of them.

So the expensive nodes are rare and the cheap nodes are many. When you add up the work for every node, the total comes out to O(n), not O(n log n).

🪜 Steps to Build a Heap (Heapify)

Here is the full plan before we write any code.

1. Start with the unordered array of size n.
2. Find the last non-leaf node. Its index is n / 2 - 1.
3. Move from that index down to index 0, one step at a time.
4. At each index, run sift-down to push that value to its correct place.
5. When the loop reaches the root and finishes, the whole array is a valid max heap.

We start at n / 2 - 1 because every index after it is a leaf. Leaves are already valid heaps. So fixing them would be wasted work.

💻 Heapify in Five Languages

Let us build a max heap from the array [3, 9, 2, 1, 4, 5]. We write a siftDown helper and a buildHeap function that calls it bottom-up.

#include <stdio.h>

// Swap two integer values
void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

// Push the node at index i down to its correct spot
void siftDown(int arr[], int n, int i) {
    while (1) {
        int largest = i;          // assume parent is largest
        int left = 2 * i + 1;     // left child
        int right = 2 * i + 2;    // right child

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

        if (largest == i) break;  // parent already largest, done

        swap(&arr[i], &arr[largest]);
        i = largest;              // continue from where it landed
    }
}

// Build a max heap from an unordered array
void buildHeap(int arr[], int n) {
    // start at the last non-leaf node, move up to the root
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, n, i);
    }
}

int main() {
    int arr[] = {3, 9, 2, 1, 4, 5};
    int n = 6;

    buildHeap(arr, n);

    printf("Max heap: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Max heap: 9 4 5 1 3 2

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

// Push the node at index i down to its correct spot
void siftDown(vector<int>& arr, int n, int i) {
    while (true) {
        int largest = i;          // assume parent is largest
        int left = 2 * i + 1;     // left child
        int right = 2 * i + 2;    // right child

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

        if (largest == i) break;  // parent already largest, done

        swap(arr[i], arr[largest]);
        i = largest;              // continue from where it landed
    }
}

// Build a max heap from an unordered array
void buildHeap(vector<int>& arr) {
    int n = arr.size();
    // start at the last non-leaf node, move up to the root
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, n, i);
    }
}

int main() {
    vector<int> arr = {3, 9, 2, 1, 4, 5};

    buildHeap(arr);

    cout << "Max heap: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    return 0;
}

Max heap: 9 4 5 1 3 2

public class BuildHeap {

    // Push the node at index i down to its correct spot
    static void siftDown(int[] arr, int n, int i) {
        while (true) {
            int largest = i;          // assume parent is largest
            int left = 2 * i + 1;     // left child
            int right = 2 * i + 2;    // right child

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

            if (largest == i) break;  // parent already largest, done

            int t = arr[i];           // swap parent with largest child
            arr[i] = arr[largest];
            arr[largest] = t;
            i = largest;              // continue from where it landed
        }
    }

    // Build a max heap from an unordered array
    static void buildHeap(int[] arr) {
        int n = arr.length;
        // start at the last non-leaf node, move up to the root
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(arr, n, i);
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 9, 2, 1, 4, 5};

        buildHeap(arr);

        System.out.print("Max heap: ");
        for (int x : arr) System.out.print(x + " ");
        System.out.println();
    }
}

Max heap: 9 4 5 1 3 2

# Push the node at index i down to its correct spot
def sift_down(arr, n, i):
    while True:
        largest = i           # assume parent is largest
        left = 2 * i + 1      # left child
        right = 2 * i + 2     # right child

        if left < n and arr[left] > arr[largest]:
            largest = left
        if right < n and arr[right] > arr[largest]:
            largest = right

        if largest == i:      # parent already largest, done
            break

        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest           # continue from where it landed


# Build a max heap from an unordered array
def build_heap(arr):
    n = len(arr)
    # start at the last non-leaf node, move up to the root
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)


arr = [3, 9, 2, 1, 4, 5]
build_heap(arr)
print("Max heap:", arr)

Max heap: [9, 4, 5, 1, 3, 2]

// Push the node at index i down to its correct spot
function siftDown(arr, n, i) {
  while (true) {
    let largest = i;          // assume parent is largest
    const left = 2 * i + 1;   // left child
    const right = 2 * i + 2;  // right child

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

    if (largest === i) break; // parent already largest, done

    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    i = largest;              // continue from where it landed
  }
}

// Build a max heap from an unordered array
function buildHeap(arr) {
  const n = arr.length;
  // start at the last non-leaf node, move up to the root
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(arr, n, i);
  }
}

const arr = [3, 9, 2, 1, 4, 5];
buildHeap(arr);
console.log("Max heap:", arr.join(" "));

Max heap: 9 4 5 1 3 2

🔎 A Quick Walk Through The Example

Our array is [3, 9, 2, 1, 4, 5] with n = 6. The last non-leaf index is 6 / 2 - 1 = 2. So we sift down indices 2, 1, 0 in that order.

This diagram shows how the values sit in the tree before we start.

Here is what happens step by step:

• At index 2, value 2 has child 5. 5 is bigger, so they swap. Index 2 becomes 5.
• At index 1, value 9 has children 1 and 4. 9 is already the largest, so nothing moves.
• At index 0, value 3 has children 9 and 5. 9 is largest, so swap. Now 3 sits at index 1 with children 1 and 4. 4 is bigger, so swap again and 3 lands at index 4. Now it has no children below, so it stops.

The root is now 9, the biggest value. The whole array is a valid max heap.

📊 Time and Space Complexity

Let us compare both ways of building a heap side by side.

⚠️ Common Mistakes

A few small mistakes catch almost everyone the first time.

• Starting sift-down from index 0 going down. The bottom-up method must start from n / 2 - 1 and move toward the root.
• Forgetting the child bounds check. Always test left < n and right < n before reading a child, or you read past the array.
• Stopping sift-down after one swap. After a swap the value may still be out of place lower down, so you must keep going.
• Mixing up the rule. In a max heap the parent is the largest. For a min heap, flip the comparison and find the smallest.

🧩 What You’ve Learned

✅ Building a heap means rearranging an unordered array so every parent follows the heap rule.

✅ The bottom-up heapify method starts at the last non-leaf node n / 2 - 1 and sift-downs each node up to the root.

✅ Sift-down pushes a node down by swapping it with its largest child until the heap rule holds.

✅ Heapify runs in O(n) time, which beats inserting nodes one by one at O(n log n).

✅ It uses O(1) extra space because all the work happens inside the same array.

🚀 What’s Next?

• Heap Operations
• Heap Sort