skip to content

questions

4

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

level: middleimportance: should knowfreq 32%

answer

  1. count the work per level, not levels
  2. how many children must you inspect?
  3. height shrinks as one over log d
  4. d-1 comparisons to pick the smallest child
  5. d over log d bottoms out near three

basics

~20 s

Raising d shrinks the height to log_d n, but every sift-down level must find the smallest of d children instead of two. Extract-min cost grows as d over log d, so a wider heap makes sift-up cheaper and sift-down dearer.

solid answer

~50 s

A d-ary heap keeps the binary heap's array layout with fan-out `d`: node `i` has children `d*i+1 .. d*i+d`. Height drops to `log_d n = log2 n / log2 d`, so anything that only sifts **up** — insert, decrease-key — gets cheaper in proportion to `1/log2 d`. Sift-down does not: at each of those fewer levels you spend `d-1` comparisons picking the smallest child plus one against the current node, so extract-min costs about `(d / log2 d) * log2 n` comparisons. That ratio bottoms out near `d = 3` and is identical for `d = 2` and `d = 4`. Asymptotically nothing moves — every bound is still O(log n) for constant d. In practice d = 4 often wins on the memory hierarchy: fewer scattered jumps, and the d siblings scanned sit contiguously, often in one cache line.

code

pseudocode · 12 lines
pseudocode
// children of i are d*i+1 .. d*i+d
sift_down(i):
    while d*i + 1 < length(a):
        best = d*i + 1
        last = min(d*i + d, length(a) - 1)
        for c in d*i+2 .. last:
            if a[c] < a[best]:
                best = c
        if a[i] <= a[best]:
            break
        swap(a[i], a[best])
        i = best

go deeper

for a junior

Know that a heap is an array with an implicit tree, and that fan-out is a parameter: children of node i are di+1 through di+d. Be able to say that both insert and extract-min remain O(log n).

for a middle

Explain the split: sift-up costs one comparison per level, sift-down costs about d per level. Derive that extract-min runs in roughly (d / log2 d) · log2 n comparisons and that this is flat between d = 2 and d = 4.

for a senior

Show why the comparison count is the wrong thing to optimise on real hardware — cache misses dominate, siblings are contiguous, depth reduction buys locality. Pick d from the measured insert-to-extract ratio rather than from a formula.

for a principal

Own the argument that fan-out is a constant-factor tuning knob, not an algorithmic improvement, and set the bar for changing it: a benchmark on production-shaped inputs showing the queue is on the critical path. Otherwise the tuning is unpaid complexity.

## 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.

  • Does raising d change the asymptotic complexity of insert or extract-min?
    No. For any constant d, both stay O(log n) and bottom-up construction stays Theta(n). Changing the logarithm's base is multiplying by a constant, so d is purely a constant-factor knob. The only way to leave O(log n) is to change the structure, not its fan-out.
  • At what d is extract-min's comparison count minimised, and why is 4 still a common choice?
    The cost factor `d / log2 d` is minimised at the continuous optimum e, so d = 3 is the comparison-count winner. Four is chosen anyway because it ties binary on comparisons while halving the levels touched, its four children sit inside one cache line, and index arithmetic with a power of two is trivial.
  • Your workload inserts twenty items for every one it extracts. Does that change the d you pick?
    Yes — strongly toward a wider heap. Insert only ever sifts up, one comparison per level, so its cost falls as `1/log2 d` with no offsetting per-level penalty. Extract-min pays the wider fan-out, but at a 20:1 ratio that penalty is amortised away across the inserts you sped up.

A wider filing cabinet has fewer shelves to climb, but every shelf you stop at holds more folders to flip through before you know which one to take.

  • Claims log base d is asymptotically better than log base 2
  • Forgets sift-down needs d-1 comparisons per level
  • Says larger d improves insert and extract-min alike
  • Treats fan-out as a free win with no cost side
  • Ignores cache lines when explaining why 4-ary wins in practice

context

open as a page

What does an indexed heap's position map buy you when a queued item's priority changes?

level: middleimportance: should knowfreq 45%

basics

~20 s

An indexed heap maps each element's identity to its current array slot, so reprioritizing a queued element costs O(log n): O(1) to locate it, then one sift. A plain heap must scan O(n) to find it first.

open as a page

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

level: seniorimportance: should knowfreq 26%

basics

~20 s

The sinking element's map entry goes stale, so a later reprioritization by identity resolves to the wrong array slot and mutates a different element's key. Nothing fails at the moment of the bug; the damage surfaces much later.

open as a page

A teammate proposes Fibonacci heaps for amortized O(1) decrease-key. How do you decide?

level: principalimportance: nice to knowfreq 20%

basics

~20 s

Ask what share of runtime the priority queue owns and how decrease-keys compare with extractions. Fibonacci heaps win on paper, but their pointer overhead and cache behaviour usually lose to an array-backed indexed heap on real inputs.

open as a page