Why does inserting into a heap usually finish far sooner than extracting, if both are O(log n)?

## Same label, different bills Insert and extract on a binary heap are both O(log n). That label is correct and it is also nearly useless for predicting which one dominates a profile. Two mechanical differences separate them. ### Difference 1 — comparisons per level **Sift-up** has no choice to make. A node has exactly one parent, so each level costs one comparison: is the rising key smaller than its parent? Swap or stop. **Sift-down** has a choice. The sinking node has up to two children, and the promoted one must be the smaller, so each level costs up to two comparisons: children against each other, then the winner against the sinking key. So a full-height sift-up costs about `log2(n)` comparisons and a full-height sift-down about `2·log2(n)`. Both are O(log n) — constants vanish in the class — but the factor of two is real work, and it is the reason this matters most when the keys are expensive to compare: a composite priority that falls back to an arrival timestamp, or a long identifier string, turns each comparison into more than a register operation. ### Difference 2 — where the nodes actually are This is the bigger effect. In a complete binary tree the levels roughly double: 1, 2, 4, 8, …, so the bottom level holds about **half** of all nodes and the bottom two levels about **three quarters**. "Height `log2(n)`" describes the deepest path, not the typical node. Now follow each operation: - **Insert** places the new record in the next free slot at the bottom and sifts it *up*. To climb even one level it must beat the key already there — and the key already there is one of the many nodes that also arrived in the crowded lower levels. For arrivals in no particular order, the expected number of swaps is a small constant, independent of `n`. The loop breaks almost immediately, most of the time. - **Extract** does the reverse. It takes the **last** element — a key that had earned its place near the bottom, so probably a large one — and puts it at the root. To stop early it must be smaller than both of its children right near the top, which is unlikely for a bottom-dweller. So sift-down usually runs most of the height. Extract's worst case is close to its typical case. The practical shape: a triage board absorbing arrivals is cheap; a board being drained is not. If you profile a workload where records arrive far more often than they are dispatched, the heap barely shows up. Flip the ratio and it does. ## The worst cases stay symmetric Early termination is a statement about typical input, not a bound. A single insert costs the full height whenever the arriving key is smaller than every key currently present — a patient more urgent than everyone on the board climbs from a leaf to the root. Feed a stream of steadily-increasing urgency and *every* insert pays the full `log2(n)`. Nothing here changes the O(log n) worst-case bound for either operation; anyone who says "insert is O(1)" has upgraded an expectation into a guarantee. That direction matters generally. Big-O is an upper bound on growth: an O(log n) label does not promise the operation ever costs `log n`, and an early-termination argument does not lower the label. Both facts can be true at once, and a good answer states both. ## Reading the fragment The attached sift-up is the whole mechanism in seven lines. Two properties are worth naming out loud: 1. **The `break` is load-bearing.** Once the rising key is no smaller than its parent, every ancestor above is already no larger than that parent by the invariant, so nothing further can be out of order. Stopping is not an optimisation shortcut — it is a proof. 2. **The loop guard is `i > 0`.** The root has no parent, and a loop that tries to compute one either wraps or reads outside the structure. Running past the root is sift-up's characteristic boundary bug, the counterpart to sift-down's forgotten right-child check. ## What to say when asked "Both are O(log n) worst case. But sift-up does one comparison per level and usually stops in the first level or two, because most nodes live at the bottom; sift-down does two comparisons per level and starts with a bottom-dweller at the root, so it usually runs deep. Same class, roughly a factor of four apart in practice — and the worst cases are still symmetric."