The Heap Property, push & pop

August 2026 · 20 min read

Part 1 gave us a shape and an addressing scheme, but nothing yet makes index 0 special. This post adds the single ordering rule that does, and derives the two public operations — push and pop — from it. The rule is one line long, and everything else in this series is a consequence of it.

The Heap Property

For a min-heap, for every node i other than the root:

a[parent(i)] <= a[i]

That is it. Equivalently, read downward: every node is <= both of its children. For a max-heap, flip the comparison to >=. Everything in this series is written for a min-heap; converting is purely a matter of reversing the comparator, and we will make that mechanical in Part 5.

Notice what the rule does not say. It says nothing about siblings. It says nothing about cousins. It says nothing about a node in the left subtree versus one in the right. It is a purely local, vertical constraint: each node looks only at its parent.

Why the Root Is the Minimum — Properly

Worth proving, because the proof is short and it tells you exactly which invariant your code must never break.

Claim. If the heap property holds everywhere, then a[0] <= a[i] for all i.

Proof. Induct on the depth of i. At depth 0 the only node is the root and a[0] <= a[0]. For depth d > 0, let p = parent(i), which sits at depth d-1. The heap property gives a[p] <= a[i], and the induction hypothesis gives a[0] <= a[p]. Chaining, a[0] <= a[i]. □

The practical reading: the minimum is at index 0 as long as no path from the root is broken. When you mutate the heap, you only need to repair the one path you disturbed. Every other path was already fine and stays fine. That is why both repair operations are O(log n) and not O(n).

push: Insert at the End, Then Bubble Up

Recall from Part 1 that completeness leaves exactly one legal slot for a new element: the next free position on the last level, which is a.size() in array terms. So the structural decision is forced — append, and completeness is preserved automatically.

What may now be violated is the ordering, and only in one place: between the new node and its parent. Every other parent-child pair in the tree is untouched. So the repair is a walk up that single path, swapping while the new value is smaller than its parent. This is sift-up.

void push(const T& value) {
    a.push_back(value);
    sift_up(a.size() - 1);
}

Trace an insert of 2 into [3, 8, 5, 12, 9, 7]:

append          [3, 8, 5, 12, 9, 7, 2]          2 sits at index 6
i=6, parent=2   a[2]=5  > 2   -> swap           [3, 8, 2, 12, 9, 7, 5]
i=2, parent=0   a[0]=3  > 2   -> swap           [2, 8, 3, 12, 9, 7, 5]
i=0             root reached  -> stop

Two swaps for a seven-element heap. The walk visits at most one node per level, so the cost is bounded by the height: O(log n).

pop: Overwrite the Root, Then Sink Down

Removing the minimum means removing index 0 — but you cannot just erase it, because that would shift the entire array and destroy the tree structure. Completeness again dictates the move: the only node that may legally disappear is the last one. So:

1. Move the last element into the root slot.
2. Shrink the array by one. Completeness is now restored.
3. The root is almost certainly too large; push it back down to where it belongs.

void pop() {
    a[0] = a.back();      // last element overwrites the root
    a.pop_back();         // shape restored
    if (!a.empty()) sift_down(0);
}

Step 3 is sift-down: repeatedly compare the node against its children, swap with the smaller child, and continue. Swapping with the smaller child is not an arbitrary choice — it is forced, and forgetting it is one of the most common heap bugs. We will see exactly why in Part 3.

Trace a pop on [2, 8, 3, 12, 9, 7, 5]:

root 2 removed; last element 5 moves up      [5, 8, 3, 12, 9, 7]
i=0  children 8, 3   smaller is 3 < 5  -> swap   [3, 8, 5, 12, 9, 7]
i=2  child    7      7 > 5              -> stop

Back to the heap we started with, and 2 was returned. One comparison pair per level again: O(log n).

The Asymmetry Worth Internalising

Sift-up and sift-down look symmetric. They are not, and the difference explains several later results.

The last row is the important one. In push, the new element is compared against a parent drawn from the upper part of the heap, and most random values lose that comparison immediately and stop after one step. In pop, the element promoted to the root came from the last level — it is, by construction, one of the largest things in the heap, so it almost always sinks the whole way back down. This is why pop is measurably more expensive than push in practice even though both are O(log n), and it is the seed of the O(n) build-heap result in Part 4.

Complexity Summary

Next

Both operations delegate to a repair routine we have described but not written. Part 3 implements sift_up and sift_down properly, proves they terminate and restore the invariant, and covers the three bugs that account for most broken hand-rolled heaps.