Build Heap from Array

Turn any unsorted array into a valid heap in O(n) using Floyd's bottom-up heapify algorithm.

Build Heap from Array

Problem: Given an unsorted array, rearrange it in-place so it satisfies the heap property (min-heap or max-heap).

Example (min-heap):

Input: [4, 1, 7, 3, 8, 5]
Output: [1, 3, 5, 4, 8, 7] (one valid min-heap arrangement)

Note

The naive approach — insert each element one by one — is O(n log n). Floyd's algorithm builds the heap bottom-up in O(n) by only running heapify on non-leaf nodes, starting from the last one.

Why Bottom-Up is O(n)

Start at the last non-leaf node (n/2 - 1) and heapify down to index 0. Most nodes are near the bottom where heapify does almost no work:

Half the nodes are leaves — 0 work.
Quarter are one level up — at most 1 swap.
Eighth are two levels up — at most 2 swaps.

The sum of this geometric series converges to O(n), not O(n log n).

Note

Inserting one-by-one takes O(n log n) because it calls heapify up on every element, and early insertions grow the heap from scratch. Bottom-up avoids this by working with the full array from the start.

How to Think About It

Approach:

Leaf nodes (indices n/2 to n-1) already satisfy the heap property trivially — they have no children to violate it.
Start at the last non-leaf (n/2 - 1) and call heapify-down, then move left toward index 0.
Why heapify down (not up)? Because you're fixing subtrees bottom-up. When you heapify node i, both its left and right subtrees are already valid heaps — so sinking i down is all that's needed.

Implementation

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

// Heapify down for min-heap: ensure arr[i] is ≤ its children
void heapifyDown(vector<int>& arr, int n, int i) {
    while (true) {
        int smallest = i;
        int left  = 2 * i + 1;
        int right = 2 * i + 2;
        if (left  < n && arr[left]  < arr[smallest]) smallest = left;
        if (right < n && arr[right] < arr[smallest]) smallest = right;
        if (smallest == i) break;
        swap(arr[i], arr[smallest]);
        i = smallest;
    }
}

// Build a min-heap in-place — O(n)
void buildMinHeap(vector<int>& arr) {
    int n = arr.size();
    // Start from last non-leaf and heapify down to root
    for (int i = n / 2 - 1; i >= 0; i--)
        heapifyDown(arr, n, i);
}

// arr = {4, 1, 7, 3, 8, 5}
// After buildMinHeap: arr = {1, 3, 5, 4, 8, 7}  (valid min-heap)
// arr[0] is always the minimum after this call

Naive O(n log n) vs Floyd's O(n)

// Naive: insert one by one — O(n log n)
void buildHeapNaive(vector<int>& arr) {
    int n = arr.size();
    // Treat arr[0..i] as a valid heap and insert arr[i+1]
    for (int i = 1; i < n; i++) {
        int j = i;
        while (j > 0 && arr[(j-1)/2] > arr[j]) {
            swap(arr[(j-1)/2], arr[j]);
            j = (j - 1) / 2;
        }
    }
}
// This is O(n log n) because each heapify-up on a heap of size i costs O(log i)

Approach	Time	Space
Insert one by one (heapify up)	`O(n log n)`	`O(1)`
Floyd's bottom-up (heapify down)	`O(n)`	`O(1)`