Offensive Security Researcher & Quantum Cryptography Analyst

Heap Sort: Building a Heap Data Structure Step by Step

Abdul Wahab Junaid
Heap Sort: Building a Heap

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

How It Works

Here’s the process I follow to build a max-heap from an arbitrary array:

  1. Compute the index of the last non-leaf node, which is $\lfloor n/2 \rfloor – 1$ for a 0-indexed array of size $n$.
  2. Starting from that index and moving backward toward index 0, call heapify on each node in turn.
  3. 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 heapify on it.
  4. Once I’ve called heapify on 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)"] --> E

Pseudocode

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

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version