Sift-Up, Sift-Down & Why They Are Correct

August 2026 · 22 min read

Two routines carry the entire weight of a binary heap. sift_up repairs a node that is too small for its position; sift_down repairs one that is too large. push, pop, build, heapsort, decrease-key and update are all thin wrappers around these two. Get them right once and the rest of the series is bookkeeping.

This post writes them properly, proves they work, and then dissects the three bugs that account for most broken hand-rolled heaps.

sift-up

Precondition: the heap property holds everywhere except possibly between node i and its parent, and the violation is that a[i] is too small. Postcondition: it holds everywhere.

void sift_up(std::size_t i) {
    T value = std::move(a[i]);              // hold the travelling element
    while (i > 0) {
        std::size_t p = (i - 1) / 2;
        if (!(value < a[p])) break;         // parent already <= value: done
        a[i] = std::move(a[p]);             // slide parent down one level
        i = p;
    }
    a[i] = std::move(value);                // drop it into its final home
}

Note the shape of this loop: it does not swap. Swapping writes three times per level (temp, a, b); the “hole-punching” formulation above writes once per level and stores the travelling value exactly once at the end. For a heap of std::string or any type with a non-trivial move, that is a real constant-factor win, and it is what the standard library implementations do.

Why it is correct. The loop invariant is: every parent-child pair in the heap is ordered, except that the hole at index i is logically occupied by value, which may be smaller than a[parent(i)]. Each iteration moves the parent into the hole — legal because the parent is larger than value, so it is certainly larger than whatever value was going to dominate — and moves the hole up one level. The loop exits either at the root (no parent to violate) or when the parent is already <= value. In both cases writing value into the hole satisfies the property. Termination is immediate: i strictly decreases and is bounded below by 0, so at most floor(log2 n) iterations.

sift-down

Precondition: both subtrees of i are valid heaps, but a[i] itself may be too large. Postcondition: the subtree rooted at i is a valid heap.

void sift_down(std::size_t i) {
    std::size_t n = a.size();
    T value = std::move(a[i]);
    while (true) {
        std::size_t l = 2 * i + 1;
        if (l >= n) break;                  // no children: i is a leaf

        std::size_t c = l;                  // c = index of the SMALLER child
        std::size_t r = l + 1;
        if (r < n && a[r] < a[l]) c = r;

        if (!(a[c] < value)) break;         // value already <= both children
        a[i] = std::move(a[c]);             // promote the smaller child
        i = c;
    }
    a[i] = std::move(value);
}

Why the smaller child, and not either one? This is the single most important line in the routine. Suppose you swapped with the larger child instead. That child is promoted to be the parent of its former sibling — and it is larger than that sibling, so you have created a fresh violation on the other side, in a subtree you already declared finished. The heap property demands the parent dominate both children; only the smaller child is guaranteed to do so. Concretely:

       9                promote 7 (the LARGER child):        7
      / \                                                   / \
     4   7             ->                                   9   4      <- 7 > 4, broken
     
       9                promote 4 (the smaller child):       4
      / \                                                   / \
     4   7             ->                                   9   7      <- correct

Termination and cost. i strictly increases each iteration and is bounded by n, so the loop runs at most the height of the tree. Each level costs at most two comparisons (one to pick the child, one against value), giving 2*floor(log2 n) comparisons worst case — twice the comparison count of sift-up per level, which is exactly the asymmetry Part 2 flagged.

The Complete Heap

With both primitives in hand, the whole structure is short:

#include <vector>
#include <utility>
#include <functional>
#include <stdexcept>

template <class T, class Compare = std::less<T>>
class BinaryHeap {
    std::vector<T> a;
    Compare less;                            // less(x,y) == true means x has higher priority

    void sift_up(std::size_t i) {
        T value = std::move(a[i]);
        while (i > 0) {
            std::size_t p = (i - 1) / 2;
            if (!less(value, a[p])) break;
            a[i] = std::move(a[p]);
            i = p;
        }
        a[i] = std::move(value);
    }

    void sift_down(std::size_t i) {
        std::size_t n = a.size();
        T value = std::move(a[i]);
        for (;;) {
            std::size_t l = 2 * i + 1;
            if (l >= n) break;
            std::size_t c = (l + 1 < n && less(a[l + 1], a[l])) ? l + 1 : l;
            if (!less(a[c], value)) break;
            a[i] = std::move(a[c]);
            i = c;
        }
        a[i] = std::move(value);
    }

public:
    explicit BinaryHeap(Compare c = Compare()) : less(c) {}

    bool        empty() const { return a.empty(); }
    std::size_t size () const { return a.size();  }

    const T& top() const {
        if (a.empty()) throw std::out_of_range("top on empty heap");
        return a[0];
    }

    void push(const T& v) { a.push_back(v);            sift_up(a.size() - 1); }
    void push(T&& v)      { a.push_back(std::move(v)); sift_up(a.size() - 1); }

    void pop() {
        if (a.empty()) throw std::out_of_range("pop on empty heap");
        a[0] = std::move(a.back());
        a.pop_back();
        if (!a.empty()) sift_down(0);
    }
};

Roughly fifty lines for a fully general priority queue. That is the whole data structure.

The Three Bugs

1. Swapping with the wrong child

Covered above, and worth restating because it is insidious: the heap still looks plausible, top() is often still correct for a while, and the corruption only surfaces several pops later when an element surfaces out of order. If your heap “mostly works”, this is the first thing to check.

2. Unsigned underflow at the root

parent(0) is (0 - 1) / 2. With std::size_t that is (SIZE_MAX)/2 — an enormous index, not -1. Any loop written as

while (a[i] < a[(i - 1) / 2]) { ... }        // BROKEN at i == 0

reads far out of bounds on the first iteration once i reaches the root. The guard must be while (i > 0), checked before the parent index is computed. Signed indices hide this bug rather than fixing it — (0-1)/2 == 0 in C++ integer division, so the loop silently compares the root against itself and merely wastes an iteration. It works by accident; do not rely on it.

3. Reading a right child that does not exist

The last internal node frequently has only a left child. The test r < n must come first and short-circuit:

if (r < n && a[r] < a[l]) c = r;        // correct: bounds check short-circuits
if (a[r] < a[l] && r < n) c = r;        // UB: reads a[r] before checking

The second form reads one past the end whenever the node has a single child. With std::vector::operator[] there is no bounds checking, so this is silent undefined behaviour that a sanitizer will catch and a casual test will not.

An Invariant Checker

Cheap, and worth calling from tests after every mutation:

bool is_valid() const {
    for (std::size_t i = 1; i < a.size(); ++i)
        if (less(a[i], a[(i - 1) / 2])) return false;   // child beats parent
    return true;
}

One linear scan checking every child against its parent. If this ever returns false, the last mutation is your culprit — which turns a mysterious wrong answer twenty operations later into an immediate, localised failure.

Next

We can now build a heap by pushing n elements one at a time, for O(n log n). Part 4 shows that you can do it in O(n) instead, using nothing but sift_down — and the proof of why is one of the prettiest arguments in elementary algorithms.