In a d-ary heap, why doesn't a shallower tree automatically make extract-min faster?

## What a d-ary heap actually changes A binary heap is an array with an ordering invariant: in a min-heap, every node's key is less than or equal to both of its children's. The tree is implicit — for 0-indexed storage, node `i` has children `2i+1` and `2i+2` and parent `(i-1)/2`. A d-ary heap changes exactly one thing: the fan-out. Node `i` has children `d*i+1 … d*i+d` and parent `(i-1)/d`. Same contiguous array, same invariant, same two repair routines — sift-up (a node that became too small walks toward the root) and sift-down (a node that became too large sinks). A binary heap is the case `d = 2`. ## The two repair routines move in opposite directions **Sift-up** compares the node with its parent, once per level. Its cost is the height: `log_d n = log2 n / log2 d` So going from d = 2 to d = 4 halves it, and to d = 8 cuts it to a third. **Sift-down** must, at every level, determine which of up to `d` children is the smallest — that is `d-1` comparisons — and then one more comparison to decide whether the node is already in place. Roughly `d` comparisons per level over `log_d n` levels: `d * log_d n = (d / log2 d) * log2 n` | d | levels visited | sift-down comparisons | sift-up comparisons | |---|---|---|---| | 2 | 1.00 · log2 n | 2.00 · log2 n | 1.00 · log2 n | | 3 | 0.63 · log2 n | 1.89 · log2 n | 0.63 · log2 n | | 4 | 0.50 · log2 n | 2.00 · log2 n | 0.50 · log2 n | | 8 | 0.33 · log2 n | 2.67 · log2 n | 0.33 · log2 n | Two readings matter. First, `d / log2 d` is minimised at the continuous optimum `e ≈ 2.718`, so **ternary** is the comparison-count champion. Second, **d = 4 spends exactly as many comparisons as binary on sift-down while touching half as many levels** — free on the metric everyone counts, strictly better on the metric that actually costs. ## Why levels cost more than comparisons A comparison of two keys already in registers is close to free. A level transition is an index jump of a multiplicative factor, which on a large heap means a different cache line, and near the leaves a different page. That miss can cost as much as dozens of comparisons. Meanwhile the `d` children of a node are stored **adjacent** to each other, so scanning all of them is one or two lines fetched once. With 8-byte keys, four children occupy 32 bytes — comfortably inside a typical 64-byte cache line. So widening the heap converts expensive scattered misses into cheap sequential comparisons. That is the whole practical argument for `d = 4` (and sometimes 8) in throughput-sensitive queues, and it is invisible to a pure comparison-count analysis. ## Picking d from the workload - **Insert-dominated** (a telemetry pipeline pushing millions of timestamped events, draining only a trickle): inserts only sift up, so wider is strictly better on both comparisons and levels. Push d to 4 or 8. - **Reprioritization-dominated**: a key that decreases also only sifts up. Same conclusion. - **Drain-dominated** (you push n items and then pop all n): sift-down runs on every pop, so stay near 2–4. - **Memory-bound with huge heaps**: depth reduction matters more the further the array spills out of cache, which pushes d up. ## What does not change For constant d, every asymptotic bound is untouched: insert and extract-min are O(log n), peek is O(1), and bottom-up construction is still Θ(n). Choosing d is a constant-factor decision, full stop. It is also not free in the other direction — a large d means a fatter partially-filled last level and more wasted comparisons when the final node has fewer than d children, which the sift-down loop must bound-check anyway. ## The trap The wrong answer is "log base d is smaller than log base 2, so it's faster." Changing the base of a logarithm is multiplication by a constant; it never changes a complexity class, and here the constant it buys on the way down is paid straight back by the per-level child scan.