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.

Related pages