Why is a heap's replace-top cheaper than an extract followed by an insert?

## The pattern this exists for Some workloads never grow or shrink their heap. A monitoring board holds the N most urgent records; every arrival that qualifies pushes one record out. A sliding window keeps a fixed roster. In all of them the operation is really *one* logical action — **swap the top for a new record** — and expressing it as "remove, then add" makes the structure do twice the work. ## What extract-then-insert actually costs Walk it on a fixed-size triage board of `n` records: 1. **Extract.** Return the root. Move the last element into the root slot, shrink to `n-1`, sift it down. That element came from the bottom, so it is typically large and typically sinks nearly the full height, at up to two comparisons per level. 2. **Insert.** Put the arriving record in the now-free slot at the bottom, grow back to `n`, sift it up, one comparison per level until it loses. Two traversals of the same height, and they partly undo each other: the first pass drags a bottom key up to the root and pushes it back down; the second drags a new key up from the bottom. ## What replace-top costs 1. Save the root's value to return. 2. Write the arriving record **directly into the root slot** — the size never changes. 3. Sift down once. One traversal. The heap property holds afterwards for the usual sift-down reason: both subtrees of the root were already valid heaps and only the root was disturbed, which is exactly sift-down's precondition. So the win is: **one sift-down instead of a sift-down plus a sift-up**, plus no shrink-and-regrow at the tail. Roughly a factor of two on the heap work. ## Be precise about what improved Both forms are O(log n). Replace-top does **not** change the complexity class, and a candidate who claims it turns the operation constant-time has made the classic direction error — confusing a constant-factor improvement with an asymptotic one. What actually improved is: - **Comparisons**, roughly halved — the lever that grows when a comparison is expensive, e.g. a priority that falls back to an arrival timestamp, or keys that are long identifiers. - **Structural churn**, eliminated — no size change, no touching the tail of the backing storage. - **Atomicity of intent**, which is the underrated one: the heap is never briefly in the `n-1` state, so there is no window in which a concurrent reader or a mid-sequence failure sees a board with a missing record. ## The ordering variant, and the free case There are two distinct pairings, and they are not interchangeable: - **Replace (pop-then-push semantics):** return the current top, then the arrival joins the heap. Always one sift-down. - **Push-then-pop semantics:** the arrival joins first, then the extreme is removed. Here a genuine shortcut exists — if the arriving key is already the extreme (smaller than the current root in a min-heap), the correct answer is the arriving key itself and **the heap need not be touched at all**. One comparison, no traversal, O(1). On a monitoring board keeping the N most urgent records, most arrivals are *not* urgent enough to belong, so this guard skips the heap entirely for the common case — a far bigger win than halving the sift. Getting the two orderings mixed up is a correctness bug, not a performance one: they return different records when the arrival ties or beats the current top. ## Failure modes to name - **Overwriting the root and forgetting the sift-down.** The invariant is violated at the top and the structure never self-repairs; every later extraction can return out-of-order records, with no error at the point of damage. - **Assuming the new key always sinks to a leaf.** It may stop at the root immediately — a key more urgent than both children stays put after two comparisons, and the loop must handle that as the normal case. - **Reaching for it first.** This is a constant-factor optimisation on one structure. If the dispatch path is dominated by serialisation or storage, halving the comparisons buys nothing. The senior move is to establish the heap is on the critical path, then apply it; the principal move is to ask whether a hand-tuned variant is worth the maintenance burden versus a plain, obviously-correct extract-then-insert that every reader recognises. ## The answer in one breath "Same O(log n), half the traversal: write the arrival at the root and sift down once instead of sinking a bottom element and then lifting a new one. It also keeps the size constant. And if the semantics are push-then-pop, check whether the arrival beats the top first — then it costs nothing at all."