In an indexed heap's sift-down, the position map is updated for only one side of each swap. What breaks?

## The invariant, stated once An indexed heap holds two structures that must agree: > For every index `i` in the array, `pos[a[i].id] == i`. This is a **coupled** invariant. The heap-order invariant (parent no greater than children) can hold perfectly while the position map is nonsense, and no operation on the array will notice. That is what makes this bug class dangerous: the structure keeps working, correctly, for every operation that enters through the root. ## Where the fragment goes wrong In the accompanying sift-down, `swap(a[i], a[best])` moves two elements. Afterwards `a[i]` holds the child that rose, and its map entry is written. `a[best]` holds the node that sank — and nothing is written for it. Then `i = best` and the loop continues, so on the next iteration the same single update again records the *rising* child, never the sinking one. The consequence: the sinking element travels the whole descent with `pos[id]` frozen at wherever it started. When the loop finally breaks, the element sits at some index `k` while the map still claims its original index. ## Why nothing fails yet After the buggy sift-down returns, the array is a valid heap. `peek-min` is right, `extract-min` is right, iteration is right, a heap-order validator passes. Every test that pushes items and pops them in order goes green. The map is wrong, but nothing has consulted it. ## How it surfaces The failure needs a second event: a reprioritization by identity, arriving at any point later — the next second, or after a thousand more operations. ``` decrease-key(id, k): i = pos[id] // stale: points at some other element now a[i].key = k // stranger's key overwritten sift_up(i) // stranger promoted ``` Three distinct symptoms follow, and which one you see depends on what happens to occupy the stale slot: 1. **Wrong element promoted.** A job you never touched moves toward the front of the queue. 2. **Silent loss of an update.** The element you meant to promote keeps its old priority; the promotion is simply gone. 3. **Corrupted keys.** The stranger's key was overwritten with a value from an unrelated element, so the queue now sorts by data that was never assigned to it. If the stale index points past the current heap size — after extractions shrank the array — you get an out-of-range access, which is the *lucky* outcome, because it fails loudly. In a scheduler whose queued build deadlines move while jobs wait, this reads as: the urgent build that was promoted still ran last, and some unrelated build jumped ahead of everything. The pop that misbehaved is many operations removed from the sift that broke the map, so the stack trace at the point of misbehaviour points at innocent code. ## Detecting it - **A validator, behind a debug flag.** Walk the array once and assert `pos[a[i].id] == i` for every `i`, plus the reverse direction: every id in the map resolves to a live index whose element carries that id. Run it after every mutating operation in tests. - **Property-based testing against a naive reference.** Implement a deliberately slow priority queue — a plain list scanned linearly — and drive both with the same random sequence of insert, extract-min, decrease-key and delete, comparing pop order. This is the technique that reliably finds coupled-invariant bugs, because it exercises the interleavings a hand-written test never thinks of. - **Test the reprioritize-after-sift interleaving explicitly.** The bug requires a sift-down that actually moved something *and then* an update by identity. A suite that only pushes and pops will never reach it. ## Designing it out The robust fix is not "remember to add the second line" — it is removing the possibility of a positional write that skips the map. Give the structure one primitive: `place(element, index)` → writes `a[index] = element` and `pos[element.id] = index` Express swap, the append in insert, the hole-fill in extract-min and delete, and the whole of both sift routines in terms of `place`. No raw array assignment survives anywhere in the file, so the invariant cannot be broken by an omission — only by deliberately bypassing the helper. A common refinement is to skip swapping entirely: hold the sinking element in a local, `place` each rising child once, then `place` the sinking element once at its final index. That is fewer writes than swapping *and* structurally incapable of the half-update. ## The general lesson Whenever a data structure keeps two representations of the same fact, every write path must update both, and the cost of an omission is deferred, silent and data-dependent. Concentrating those writes in a single chokepoint is worth more than any amount of care distributed across the call sites.