In a min-heap sift-down, why must you swap the node with its smaller child, not its left child?

## What sift-down is actually doing Sift-down repairs a heap in which **exactly one** node may violate the invariant, and both of its subtrees are already valid heaps. That precondition is the whole reason a single root-to-leaf path is enough work: everything off the path was already correct and stays correct. The repair step is a promotion. The sinking node hands its position to one of its children, and that child now sits above *both* of the old children — its own subtree, and its former sibling's subtree. So the promotion must satisfy a specific condition: **the promoted key must be no larger than the sibling it is promoted over.** In a min-heap there is exactly one child that always satisfies that condition — the smaller one. ## The bug, traced on a triage board Take a triage board kept as a min-heap on priority score (lower is more urgent): ``` scores: [2, 3, 20, 9, 4, 30, 25] 2 / \ 3 20 / \ / \ 9 4 30 25 ``` Extract the top. Score 2 is returned, the last element (25) moves into the root, and the heap shrinks to six: ``` scores: [25, 3, 20, 9, 4, 30] ``` Now run the fragment attached to this question, the one that always takes the left child. - At the root: left child is 3. `3 < 25`, so swap. → `[3, 25, 20, 9, 4, 30]`, continue from position of 25. - There: left child is 9. `9 < 25`, so swap. → `[3, 9, 20, 25, 4, 30]`, continue. - No left child exists below → stop. Draw the result: ``` 3 / \ 9 20 / \ / 25 4 30 ``` Node 9 sits above node 4. The heap property is broken — and it is broken two levels down from where the sift began, on the branch the code never looked at. Run the correct version and 4 gets promoted instead, giving `[3, 4, 20, 9, 25, 30]`, a valid heap. ## Why it is a *silent* corruption Notice what did **not** go wrong: the root still holds 3, the true minimum. Peek returns the right answer. The next extract-min also returns the right answer. The board keeps looking healthy. The damage only becomes visible when the sift eventually reaches the corrupted region and a patient with score 9 is dispatched ahead of a patient with score 4 — an out-of-order dequeue with no stack trace and no obvious culprit. This is why "my extract returns the smallest key, so my heap is fine" is not a test. The only reliable check is a **property assertion over the whole structure**: for every internal position, the key is less than or equal to each existing child. That is a linear scan, cheap to run in a test after a randomised sequence of inserts and extracts, and it localises the violation immediately. ## The boundary the same loop must respect A complete tree has one awkward node: the last internal node may have a **left child but no right child**. That is not an exotic case — it happens for every heap with an even number of elements. So the child-selection step cannot blindly read the right child: 1. If the left child index is out of range, the node is a leaf → stop. 2. Otherwise start with the left child as the candidate. 3. **Only if** the right child index is in range, compare and take the right child if it is strictly smaller. 4. Swap with the candidate if the candidate is smaller than the sinking key; otherwise stop. Skipping step 3's range guard reads past the end of the live region — which, depending on how the backing storage is managed, either throws or, far worse, compares against stale data from an element that was already extracted. The stale-data variant produces exactly the same silent corruption as the wrong-child bug. ## Comparison budget Each level of a correct sift-down costs up to two key comparisons: one to pick the smaller child, one to decide whether to swap. Over a height of about `log2(n)` that is roughly `2·log2(n)` comparisons in the worst case — still O(log n), since constants do not change the class, but worth knowing when keys are expensive to compare (long identifiers, composite priority-then-timestamp tie-breakers). The buggy left-child version is *cheaper* per level, which is a useful reminder that a comparison count is not a correctness argument. ## The one-sentence version Promote the smaller child, because the promoted node becomes the parent of the other one — and check the right child exists before you look at it.