Heapify & Heap Sort: O(n) Build and In-Place Sorting

Heapify turns an unsorted array into a valid heap, and surprisingly it runs in O(n) — faster than the O(n log n) you’d expect from inserting one at a time. Once you have that heap, heap sort repeatedly extracts the extreme element to produce a sorted array in place in O(n log n) time with only O(1) extra space. This page assumes the sift-down routine from heap operations.

Heapify: build a heap in O(n)

The trick (from heap operations): instead of inserting elements one by one, take the raw array as-is and sift down every non-leaf node, from the last non-leaf at index n/2 - 1 back to the root. Leaves (the second half of the array) are already trivial one-element heaps, so we skip them.

void siftDown(std::vector<int>& a, int i, int n) {
    while (true) {
        int l = 2*i + 1, r = 2*i + 2, largest = i;
        if (l < n && a[l] > a[largest]) largest = l;   // max-heap
        if (r < n && a[r] > a[largest]) largest = r;
        if (largest == i) break;
        std::swap(a[i], a[largest]);
        i = largest;
    }
}
void buildMaxHeap(std::vector<int>& a) {
    int n = (int)a.size();
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
}

void siftDown(int[] a, int i, int n) {
    while (true) {
        int l = 2*i + 1, r = 2*i + 2, largest = i;
        if (l < n && a[l] > a[largest]) largest = l;   // max-heap
        if (r < n && a[r] > a[largest]) largest = r;
        if (largest == i) break;
        int t = a[i]; a[i] = a[largest]; a[largest] = t;
        i = largest;
    }
}
void buildMaxHeap(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
}

function siftDown(a, i, n) {
  while (true) {
    const l = 2*i + 1, r = 2*i + 2;
    let largest = i;
    if (l < n && a[l] > a[largest]) largest = l;   // max-heap
    if (r < n && a[r] > a[largest]) largest = r;
    if (largest === i) break;
    [a[i], a[largest]] = [a[largest], a[i]];
    i = largest;
  }
}
function buildMaxHeap(a) {
  const n = a.length;
  for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(a, i, n);
}

def sift_down(a, i, n):
    while True:
        l, r, largest = 2*i + 1, 2*i + 2, i
        if l < n and a[l] > a[largest]: largest = l   # max-heap
        if r < n and a[r] > a[largest]: largest = r
        if largest == i:
            break
        a[i], a[largest] = a[largest], a[i]
        i = largest

def build_max_heap(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)

Why it’s O(n), not O(n log n)

Sift-down cost depends on a node’s height, not the tree’s height. Nodes near the bottom (the majority) sift down only a step or two; only the root can travel the full log n. Summing the work — n/2 nodes at height 0, n/4 at height 1, n/8 at height 2, … — gives n · Σ (h / 2^h), and that series converges to a constant. The total is therefore O(n).

For beginners: Inserting n items one by one really is O(n log n). Heapify is faster precisely because it works bottom-up on the existing array, where most nodes barely move.

Heap sort: sort in place using a max-heap

Heap sort has two phases:

Build a max-heap from the array — O(n). Now the largest element is at index 0.
Repeatedly swap the root (the max) with the last unsorted element, shrink the heap by one, and sift the new root back down. Each extraction parks the next-largest value into its final sorted position at the end of the array.

After n - 1 extractions the array is sorted ascending — using no extra array.

void heapSort(std::vector<int>& a) {
    int n = (int)a.size();
    buildMaxHeap(a);                 // phase 1: O(n)
    for (int end = n - 1; end > 0; end--) {
        std::swap(a[0], a[end]);     // park max at the end
        siftDown(a, 0, end);         // restore heap on a[0..end-1]
    }
}

void heapSort(int[] a) {
    int n = a.length;
    buildMaxHeap(a);                 // phase 1: O(n)
    for (int end = n - 1; end > 0; end--) {
        int t = a[0]; a[0] = a[end]; a[end] = t;  // park max
        siftDown(a, 0, end);         // restore heap on a[0..end-1]
    }
}

function heapSort(a) {
  const n = a.length;
  buildMaxHeap(a);                   // phase 1: O(n)
  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]]; // park max at the end
    siftDown(a, 0, end);             // restore heap on a[0..end-1]
  }
  return a;
}

def heap_sort(a):
    n = len(a)
    build_max_heap(a)                # phase 1: O(n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]  # park max at the end
        sift_down(a, 0, end)         # restore heap on a[0..end-1]
    return a

Pitfall: In phase 2 you must sift down over the shrinking range a[0..end-1], not the full array — otherwise you’d drag already-sorted values back into the heap. That’s why siftDown takes the current size end.

Heap sort vs the others

Property	Heap sort	Merge sort	Quick sort
Time (worst)	O(n log n)	O(n log n)	O(n²)
Extra space	O(1)	O(n)	O(log n)
Stable?	No	Yes	No

Heap sort’s superpower is its guaranteed O(n log n) with O(1) extra space — no worst-case blow-up like quicksort, no extra array like merge sort. Its downside is poor cache behaviour (it jumps around the array) and instability, so library sorts usually prefer introsort or Timsort. For the standalone topic, see heap sort.

Going deeper: Use a max-heap to sort ascending and a min-heap to sort descending. The extreme element you repeatedly remove ends up at the far end, so the heap’s direction is the opposite of the final order.

Ready to apply heaps? Try the heap exercises.