In a 0-indexed array heap, why are a node's children at 2i+1 and 2i+2 and its parent at (i-1)/2?

## Where the formulas come from An implicit heap stores no tree nodes at all. It writes the complete tree into a flat array in **level order**: the root, then level 1 left-to-right, then level 2, and so on. Everything else follows from counting. A complete binary tree has `2^L` nodes on level `L` (root = level 0), so levels `0..L-1` together hold `2^L - 1` nodes. Therefore **level `L` begins at index `2^L - 1`** and ends at `2^(L+1) - 2`. Take node at index `i` on level `L`. It is the `k`-th node on that level, counting from zero: ``` k = i - (2^L - 1) ``` In a complete tree, the `k`-th node of a level parents the `2k`-th and `(2k+1)`-th nodes of the next level — each node contributes exactly two children, in order. Level `L+1` begins at `2^(L+1) - 1`, so: ``` left = (2^(L+1) - 1) + 2k = 2^(L+1) - 1 + 2(i - 2^L + 1) = 2^(L+1) - 1 + 2i - 2^(L+1) + 2 = 2i + 1 right = 2i + 2 ``` The `2^L` terms cancel, which is why the rule is uniform across every level and needs no knowledge of `L` at runtime. Inverting `left = 2i + 1` and `right = 2i + 2` gives a single formula for both: `parent(i) = floor((i - 1) / 2)`. ## Boundaries that bite - **The root has no parent.** With true flooring, `floor((0-1)/2) = -1`. With truncation toward zero, the same expression yields `0` and the root becomes its own parent — an infinite loop in any upward walk. Guard with `i > 0` before ever calling `parent`; do not rely on the division's rounding behaviour. - **Children may not exist.** `2i+1` and `2i+2` are valid only when they are `< n`. A node is a leaf exactly when `2i + 1 >= n`. - **The last internal node** is at index `floor(n/2) - 1`; every index from `floor(n/2)` to `n-1` is a leaf. That is roughly half the array, and it is why the leaf count is about `n/2`. - **Overflow.** For very large heaps `2i + 2` can exceed the index type's range before `n` does. Where that matters, compute `left = i + i + 1` on a wide type or bound `n`. ## The 1-based scheme, and the mixup The alternative layout wastes slot 0 and puts the root at index 1. Then level `L` starts at index `2^L`, and the same counting argument gives: ``` left(i) = 2i, right(i) = 2i + 1, parent(i) = floor(i / 2) ``` It is genuinely tidier — the children formulas are a shift and a shift-or-one, and `parent` needs no subtraction — which is why textbook pseudocode often uses it. It is also the source of the most instructive bug in this topic. Suppose a matchmaking service keeps its rating pool 0-indexed, but someone copies `parent(i) = i / 2` out of a textbook. Trace it: index 1 maps to 0, which happens to be correct. Index 2 maps to 1 — but index 2's real parent is `(2-1)/2 = 0`; index 1 is its **sibling**. Index 4 maps to 2, while its real parent is 1; index 2 is its aunt. Every even index gets a wrong ancestor. And nothing crashes: all the indices are in range, the array stays the same size, and every operation returns. The structure simply stops being a heap in places, so occasionally the extracted "lowest-rated waiting player" is not the lowest — a matchmaking bug that surfaces as unfair pairings weeks later, not as a stack trace. The mirror bug is equally quiet: using `2i` and `2i+1` for children in a 0-indexed array makes node 0 its own left child. The defence is a cheap `isHeap` assertion in tests — scan `i` from 0 to `floor(n/2) - 1` and verify the invariant against both in-range children, O(n) — plus picking **one** convention and writing the three formulas in a single place rather than inlining the arithmetic at each use site. ## Why this trick is worth it The payoff is that navigation is arithmetic instead of memory: no child pointers to store, no parent pointer to maintain, no per-node allocation, and no way for the structure to become internally inconsistent through a dangling link. The price is that the tree must stay **complete** — the formulas assume slots `0..n-1` are all occupied — and that elements move as the heap changes, so no stable reference to an element survives an operation unless you maintain a separate index.