I wanted to write a dedicated article just for this one phase of Heap Sort, because the first time I studied it, I assumed building a heap from an unsorted array would cost $O(n \log n)$ — after all, I’m calling a $O(\log n)$ operation ($\texttt{heapify}$) roughly $n/2$ times. It genuinely surprised me to learn this intuition is wrong: building a heap from scratch, done correctly with a bottom-up approach, actually only costs $O(n)$. This article is my attempt to explain that surprising result clearly, since I think the proof is one of the more elegant “gotcha” moments in algorithm analysis.
History and Background
The bottom-up heap construction technique I cover here is generally credited to Robert W. Floyd, who published it in 1964 in Communications of the ACM, shortly after J.W.J. Williams introduced the binary heap and Heap Sort earlier that same year. I find the timing here interesting — the heap and Heap Sort were barely a few months old before Floyd showed how to build the initial heap far more efficiently than the naive insertion-based approach that Williams’ original presentation implied.
This linear-time construction technique became so standard that most modern algorithms textbooks, including CLRS, present Floyd’s bottom-up method as the way to build a heap, with the slower insertion-based method mentioned mainly as a contrast to highlight why the bottom-up approach is preferable.
Problem Statement
The problem I’m solving here is narrower than full sorting: given an arbitrary, unsorted array of $n$ elements, rearrange it in-place so that it satisfies the max-heap property — every parent node’s value must be greater than or equal to the values of its children.
I want to do this as efficiently as possible, since building the heap is the first phase of Heap Sort, and any inefficiency here directly adds to the total sorting time.
Core Concepts
- Non-leaf node: Any node in the heap that has at least one child. In a 0-indexed array of size $n$, the non-leaf nodes are exactly those at indices $0$ through $\lfloor n/2 \rfloor – 1$.
- Leaf node: A node with no children, trivially satisfying the heap property on its own (a single-element “subtree” is always a valid heap).
- Bottom-up construction: Processing nodes in reverse order — from the last non-leaf node up to the root — so that by the time I call
heapifyon any node, its child subtrees are already guaranteed to be valid heaps. - Heapify (sift-down): The repair procedure that fixes the heap property at a single node, assuming its children are already valid heap roots.
How It Works
Here’s the process I follow to build a max-heap from an arbitrary array:
- Compute the index of the last non-leaf node, which is $\lfloor n/2 \rfloor – 1$ for a 0-indexed array of size $n$.
- Starting from that index and moving backward toward index 0, call
heapifyon each node in turn. - Because I process nodes in this specific order (bottom-up, right-to-left within each level), every node’s children are already guaranteed to be valid heaps by the time I call
heapifyon it. - Once I’ve called
heapifyon index 0 (the root), the entire array satisfies the max-heap property.
Working Principle
The key realization that makes this efficient is this: I never need to call heapify on leaf nodes, since a single element is trivially already a valid heap. Roughly half of all nodes in a complete binary tree are leaves, so I immediately skip about half the array.
Beyond that, the deeper insight is about where the expensive heapify calls happen. heapify calls near the bottom of the tree (close to the leaves) are cheap, since there’s very little height left for an element to sift down through. Only the calls near the very top of the tree — the root and its immediate children — could potentially cost close to $O(\log n)$. Since there are exponentially fewer nodes as I go up the tree (only 1 node at the root, 2 at the next level, 4 at the next, and so on), the expensive calls are rare, and the cheap calls are common. This imbalance is exactly what collapses the total cost from the naively expected $O(n \log n)$ down to $O(n)$.
Mathematical Foundation
I want to derive the $O(n)$ bound carefully, since this is the heart of what makes this topic interesting.
In a heap of $n$ elements, the number of nodes at height $h$ (where height is measured from the leaves, so leaves are height 0) is at most:
$$ \left\lceil \frac{n}{2^{h+1}} \right\rceil $$
The cost of calling heapify on a node at height $h$ is $O(h)$, since in the worst case, the element sifts down through $h$ levels before settling.
So the total cost of building the heap is bounded by:
$$ T_{\text{build}}(n) = \sum_{h=0}^{\lfloor \log n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil O(h) $$
I can simplify this by factoring out $n$ and bounding the ceiling:
$$ T_{\text{build}}(n) = O\left(n \sum_{h=0}^{\lfloor \log n \rfloor} \frac{h}{2^h}\right) $$
Now I use a classic result about infinite series — the sum $\sum_{h=0}^{\infty} \frac{h}{2^h}$ converges to a constant. Specifically, using the general formula for $\sum_{h=0}^{\infty} h x^h = \frac{x}{(1-x)^2}$ with $x = 1/2$:
$$ \sum_{h=0}^{\infty} \frac{h}{2^h} = \frac{1/2}{(1 – 1/2)^2} = \frac{1/2}{1/4} = 2 $$
Since this infinite sum converges to the constant 2, my finite sum (which is bounded by the infinite one) is also $O(1)$. Substituting back:
$$ T_{\text{build}}(n) = O(n \cdot O(1)) = O(n) $$
This confirms that building a heap from an arbitrary array runs in linear time — a much tighter bound than the $O(n \log n)$ I’d get from naively assuming every heapify call costs the maximum possible $O(\log n)$.
Diagrams
Here’s the overall flow of the bottom-up build process:
flowchart TD
A[Unsorted Array of size n] --> B["Start at index floor(n/2) - 1 (last non-leaf node)"]
B --> C[Call heapify at current index]
C --> D[Move to previous index]
D --> E{Index >= 0?}
E -- Yes --> C
E -- No --> F[Array is now a valid Max-Heap]And here’s a diagram illustrating why most heapify calls are cheap — the number of nodes shrinks exponentially as height increases:
flowchart LR
A["Height 0 (leaves): ~n/2 nodes, cost O(0)"] --> E[Total cost dominated by lower levels]
B["Height 1: ~n/4 nodes, cost O(1)"] --> E
C["Height 2: ~n/8 nodes, cost O(2)"] --> E
D["Height log(n) (root): 1 node, cost O(log n)"] --> EPseudocode
BUILD-MAX-HEAP(A, n)
for i = floor(n/2) - 1 down to 0
HEAPIFY(A, n, i)
HEAPIFY(A, n, i)
largest = i
left = 2*i + 1
right = 2*i + 2
if left < n and A[left] > A[largest]
largest = left
if right < n and A[right] > A[largest]
largest = right
if largest != i
swap A[i] and A[largest]
HEAPIFY(A, n, largest)
Step-by-Step Example
I’ll trace through the array:
$$ [4, 10, 3, 5, 1] $$
Here $n = 5$, so the last non-leaf node is at index $\lfloor 5/2 \rfloor – 1 = 1$.
Call heapify(A, 5, 1): Node at index 1 has value 10. Its left child (index 3) is 5, and it has no right child (index 4 would be out of range for this node — wait, index 4 exists in the array but is the right child of index 1 only if $2(1)+2=4$, which is valid here). Left child (index 3) = 5, right child (index 4) = 1. Since $10 > 5$ and $10 > 1$, no swap is needed. Array remains: $[4, 10, 3, 5, 1]$.
Call heapify(A, 5, 0): Node at index 0 has value 4. Left child (index 1) = 10, right child (index 2) = 3. The largest among these is 10 (index 1), so I swap indices 0 and 1 → $[10, 4, 3, 5, 1]$. I then recursively call heapify on index 1 (value now 4). Its left child (index 3) = 5, and it has no valid right child within this recursive check in the sense that I compare against both existing children: right child (index 4) = 1. Since $5 > 4$, I swap indices 1 and 3 → $[10, 5, 3, 4, 1]$. Recursing further on index 3, which is a leaf (no children within range), so the process stops.
Final heap array:
$$ [10, 5, 3, 4, 1] $$
This matches exactly what my tested C program produced, which reported the trace as: after heapify at index 1, the array is unchanged at 4 10 3 5 1; after heapify at index 0, the array becomes 10 5 3 4 1, which is the final max-heap.
Time Complexity
- Best Case: $O(n)$ — the bottom-up construction always performs the same sequence of
heapifycalls regardless of the specific values in the input, though the number of swaps within each call may vary; the asymptotic bound remains $O(n)$ regardless. - Average Case: $O(n)$ — consistent with the tight mathematical bound derived above.
- Worst Case: $O(n)$ — even in the worst case (where every
heapifycall does the maximum possible sifting), the geometric argument above shows the total remains linear.
Space Complexity
Building a heap in-place requires:
$$ O(1) $$
auxiliary space for the swap operations, plus $O(\log n)$ recursive call stack space if heapify is implemented recursively (as in my tested implementation). An iterative heapify implementation would reduce this to strictly $O(1)$.
Correctness Analysis
I prove correctness by induction on the order in which nodes are processed — specifically, processing from the last non-leaf node down to the root (index 0), in decreasing index order.
Base case: All leaf nodes (indices from $\lfloor n/2 \rfloor$ to $n-1$) are trivially valid max-heaps of size 1, requiring no processing.
Inductive step: When I call heapify on node $i$, I claim both of its children (if they exist) are already roots of valid max-heaps. This holds because, in a 0-indexed array, any child of node $i$ has a strictly larger index than $i$ (since child indices are $2i+1$ and $2i+2$, both greater than $i$ for $i \geq 0$), and I always process nodes in decreasing index order — meaning every child has already been processed (or is a leaf, satisfying the base case) by the time I reach node $i$. Given that both children are valid heap roots, heapify‘s own correctness (established in my article on maintaining the heap property) guarantees that after the call, the subtree rooted at $i$ becomes a valid max-heap.
By induction, once I’ve processed index 0 (the root), the entire array satisfies the max-heap property.
Advantages
- Achieves linear time, $O(n)$, which is asymptotically optimal — I can’t build a heap from arbitrary data any faster than reading through it once.
- Simple to implement: a single loop over half the array, calling an already-understood
heapifysubroutine. - Forms the necessary first phase for Heap Sort, and is independently useful whenever I need to convert raw data into heap form for use in a priority queue.
- In-place, requiring no extra array beyond the input itself.
Disadvantages
- The linear-time bound relies specifically on the bottom-up approach — using the naive one-at-a-time insertion approach instead costs $O(n \log n)$, so the “right” implementation matters.
- The proof of the $O(n)$ bound, while elegant, is less immediately intuitive than a simple counting argument, which can make this phase harder to explain or verify informally compared to other parts of Heap Sort.
- Still requires $O(\log n)$ recursive stack space per call if implemented recursively, which is a minor overhead compared to a fully iterative version.
Applications
- The mandatory first phase of Heap Sort, directly enabling its $O(n \log n)$ total running time.
- Efficiently initializing a priority queue from a pre-existing collection of elements (bulk construction), rather than inserting elements one at a time.
- Any algorithm that needs to repeatedly extract the maximum (or minimum) from a large, fixed initial dataset, such as certain graph algorithms that seed their priority queues from an entire vertex or edge set at once.
Implementation in C
Here is my tested implementation of the bottom-up build-heap procedure, with tracing output added to illustrate each step:
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Restores the max-heap property at index i, assuming child subtrees
// are already valid heaps (which bottom-up processing guarantees)
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// Builds a max-heap from an arbitrary array in O(n) time,
// processing nodes from the last non-leaf up to the root
void buildMaxHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
printf("After heapify at index %d: ", i);
printArray(arr, n);
}
}
int main() {
int arr[] = {4, 10, 3, 5, 1};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Initial array: ");
printArray(arr, n);
buildMaxHeap(arr, n);
printf("Final max-heap: ");
printArray(arr, n);
return 0;
}
Sample Input and Output
Input:
4 10 3 5 1
Output (verified by compiling and running the code above):
Initial array: 4 10 3 5 1
After heapify at index 1: 4 10 3 5 1
After heapify at index 0: 10 5 3 4 1
Final max-heap: 10 5 3 4 1
Optimization Techniques
- Iterative heapify: Removing recursion in favor of a loop eliminates the $O(\log n)$ call stack overhead, keeping auxiliary space at strictly $O(1)$.
- Parallelization: Since each subtree at a given level is independent of others at the same level,
heapifycalls within a single level of the bottom-up pass can be parallelized, which is useful for building heaps from very large datasets. - Skipping unnecessary comparisons: Some implementations cache child indices or avoid recomputation of $2i+1$ and $2i+2$ across repeated calls, though modern compilers often optimize this automatically.
- Choosing the right base structure: If elements are already partially sorted or already close to heap order, some specialized construction techniques can do even less work in practice, though the asymptotic bound remains $O(n)$ regardless.
Common Mistakes
- Starting the loop from index 0 instead of $\lfloor n/2 \rfloor – 1$. Processing leaf nodes unnecessarily wastes time (though it doesn’t break correctness, since leaves are already valid heaps and heapify on a leaf does nothing).
- Processing nodes in the wrong order (root to leaves) instead of bottom-up. This breaks the entire premise of the algorithm — if children haven’t been heapified yet when I process their parent, the correctness proof no longer holds, and the result won’t be a valid heap.
- Assuming the naive insertion-based construction (
insertone element at a time into a growing heap) is equivalent in performance. It’s asymptotically worse — $O(n \log n)$ instead of $O(n)$ — even though it produces the same final valid heap structure. - Miscalculating the last non-leaf index. Off-by-one errors here (using $n/2$ instead of $n/2 – 1$, or forgetting integer division truncation) can cause out-of-bounds access or redundant heapify calls.
- Forgetting this is just the first phase. Building a valid max-heap doesn’t sort the array — I still need the extraction phase (covered in my main Heap Sort article) to actually produce sorted output.
Further Reading
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), MIT Press — https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- R.W. Floyd, “Algorithm 245: Treesort 3”, Communications of the ACM, 1964 — https://dl.acm.org/doi/10.1145/355588.365103
- J.W.J. Williams, “Algorithm 232 – Heapsort”, Communications of the ACM, 1964 — https://dl.acm.org/doi/10.1145/512274.512284
- Wikipedia, “Binary heap” — https://en.wikipedia.org/wiki/Binary_heap
- Wikipedia, “Heapsort” — https://en.wikipedia.org/wiki/Heapsort
