Binary Heaps and Priority Queues: Sift Up, Sift Down, and Build-Heap

The array layout: where the children are

Because the tree is complete (filled level by level, left to right), it fits an array with no gaps. With 0-based indexing:

• left child of i is 2i + 1
• right child of i is 2i + 2
• parent of i is (i - 1) / 2 (integer division)

The heap property comes in two flavours: in a min-heap every node is ≤ its children (so the minimum sits at index 0); in a max-heap every node is ≥ its children (maximum at index 0). Note carefully what the property does not say: it says nothing about left versus right siblings, and nothing about depth ordering across different subtrees. A heap is not a search structure — finding an arbitrary value still takes O(n). It answers exactly one question fast: what is the smallest (or largest) item?

// Min-heap on a plain int array. Size is the current element count.
int a[16];
int n = 0;                       // a[0..n-1] is the heap

inline int parent(int i) { return (i - 1) / 2; }
inline int left(int i)   { return 2 * i + 1; }
inline int right(int i)  { return 2 * i + 2; }

Insert = place at the end, sift up

To insert, put the new value in the next free slot (keeping the tree complete) and sift up: while it is smaller than its parent, swap. Each swap fixes the one violated edge and cannot break the rest, because the new value was already ≥ everything below its old position.

Trace — insert 2 into the min-heap [5, 8, 6, 9, 12]:

1. Append: [5, 8, 6, 9, 12, 2], index 5, parent (5−1)/2 = 2 (value 6).
2. 2 < 6 → swap: [5, 8, 2, 9, 12, 6], index 2, parent 0 (value 5).
3. 2 < 5 → swap: [2, 8, 5, 9, 12, 6], index 0 — root. Stop.

Cost: at most one comparison per level ⇒ O(log n). Best case (value already ≥ parent) is O(1).

void siftUp(int i) {              // used by insert
    while (i > 0 && a[parent(i)] > a[i]) {
        std::swap(a[i], a[parent(i)]);
        i = parent(i);
    }
}
void insert(int v) { a[n++] = v; siftUp(n - 1); }

Pop = move the last leaf to the root, sift down

You cannot remove the root and leave a hole — the array must stay contiguous and the tree complete. So: save the root (the answer), move the last element to index 0, shrink the heap by one, then sift down: repeatedly swap the node with its smaller child until both children are ≥ it.

Why the smaller child? Swapping with the larger child of a min-heap can put a value above something smaller — breaking the property. Choosing the smaller child is the detail exam questions probe.

Trace — pop from [2, 8, 5, 9, 12, 6]:

1. Answer is 2. Move last (6) to root, shrink: [6, 8, 5, 9, 12].
2. Children of 0: 8 (idx 1), 5 (idx 2). Smaller is 5. 6 > 5 → swap: [5, 8, 6, 9, 12].
3. Node now index 2, children: none (4 and 5 are out of range with n = 5). Stop.

Cost: O(log n) — the path from root to leaf has ⌊log₂ n⌋ levels.

void siftDown(int i) {            // used by pop and build-heap
    while (true) {
        int smallest = i;
        if (left(i)  < n && a[left(i)]  < a[smallest]) smallest = left(i);
        if (right(i) < n && a[right(i)] < a[smallest]) smallest = right(i);
        if (smallest == i) break;              // heap property holds
        std::swap(a[i], a[smallest]);
        i = smallest;                          // descend
    }
}
int pop() {
    int top = a[0];
    a[0] = a[--n];                             // last leaf becomes root
    siftDown(0);
    return top;
}

Build-heap: why it is O(n), not O(n log n)

Turning an arbitrary array into a heap: sift down every internal node, starting from the last parent (index n/2 − 1) and walking back to 0. Leaves are already valid one-element heaps, so they are skipped.

The complexity argument is the part worth being able to reproduce: a node at height h costs O(h) to sift down, and at most ⌈n / 2^(h+1)⌉ nodes have that height. Summing n · Σ h/2^(h+1) over heights converges to a constant — the series Σ h/2^h = 2 — so the total is O(n). The intuition: half the nodes are leaves (height 0, free to fix), and only a handful of nodes near the root can cascade the full log n.

This is why inserting n items one by one (O(n log n)) is the worse way to build a heap, and the discrepancy is a classic short-answer question.

void buildHeap() {                // from arbitrary a[0..n-1]
    for (int i = n / 2 - 1; i >= 0; --i)
        siftDown(i);                          // last parent down to root
}

Priority queues and heapsort

A priority queue is the abstract data type — insert item with priority, remove the highest-priority item — and the binary heap is its standard implementation, exactly as std::priority_queue is specified (a max-heap by default). std::greater<T> flips it to a min-heap:

std::priority_queue<int> maxpq;                              // max on top
std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;

Heapsort is build-heap followed by n pops that each write the removed root into the vacated tail slot: build (O(n)) plus n pops at O(log n) gives O(n log n) worst case, in place, but not stable. The exam contrast worth memorizing: heapsort guarantees n log n where quicksort does not, but quicksort's cache behavior wins in practice.

The mistakes that cost marks

• Sifting down against the larger child in a min-heap — produces a valid-looking array with a small value buried under a big one; the bug is silent until the grader checks the property.
• Forgetting --n before or after moving the last element in pop — either the stale last element gets sifted again or the heap keeps an extra element; off-by-one central.
• Building by n inserts and reporting O(n) — insert is O(log n) each, so that construction is O(n log n); only the sift-down-from-last-parent loop is O(n).
• Stopping sift-down at left(i) < n but reading right(i) unguarded — reads one past the heap end when the left child is the last element; the guard must cover both children.
• Treating a heap as sorted. [1, 5, 3, 8, 6] is a valid min-heap and visibly not sorted. Level order is not sort order — the only guaranteed position is the root.

Exercises with solutions

Work through each question before opening the solution below it.

Which C++ standard does this page assume?

Standard C++17. C++ began as C with Classes in 1979 and first shipped commercially in 1985; what a compiler flag actually selects today is one of the ISO revisions below, and the committee has published a new one every 3 years since 2011. Build these listings with -std=c++17 and they compile as written.

Common questions

Where can I check this against the language itself?

Nothing on this page outranks the standard or the library reference. When this page and one of these disagree, they are right and we want to know.

• cppreference — the C++ standard library referenceThe fastest correct answer for what a container or algorithm actually guarantees.
• isocpp.org — the Standard C++ FoundationThe FAQ and the core guidelines, written by the people who define the language.
• ISO/IEC JTC1/SC22/WG21 — the C++ standards committeeWorking drafts of the standard itself, free to read, when the wording is the question.
• GCC online documentationWhat -Wall, -Wextra and the sanitizers used on these listings actually check.
• Microsoft Learn — C++ language documentationThe MSVC view, for readers whose lab machines build with Visual Studio.

Related pages