D-ary Heap
A binary heap is a heap with d = 2. Let every node have d children instead, still packed into an array with children of slot i at d i + 1 through d i + d, and the tree gets shallower: log_d n levels. Sifting up compares with one parent per level, so it gets cheaper. Sifting down has to find the smallest of d children at every level, so it gets dearer. That is the whole trade, and it pays whenever sift-up operations outnumber extracts, which is exactly the shape of Dijkstra on a dense graph: many decrease-key calls per extract-min. A 4-heap is the common choice in practice.
Turn 42, 17, 8, 31, 5, 26, 12, 3, 19, 9 into a 3-ary min-heap in place. Slot i's children are slots 3 x i + 1 to 3 x i + 3, so the last slot with a child is 2. Sift each slot down from there back to the root; the leaves are heaps already.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 4, with their answers.
Slot 2 holds 8 above children 3, 19, 9. What happens?
Answer: Swap with 3, the smallest child. Find the smallest of the 3 children first; swap only if it is smaller than the node.
Slot 1 holds 17 above children 5, 26, 12. What happens?
Answer: Swap with 5, the smallest child. Find the smallest of the 3 children first; swap only if it is smaller than the node.
Slot 0 holds 42 above children 5, 3, 31. What happens?
Answer: Swap with 3, the smallest child. Find the smallest of the 3 children first; swap only if it is smaller than the node.
Slot 2 holds 42 above children 8, 19, 9. What happens?
Answer: Swap with 8, the smallest child. Find the smallest of the 3 children first; swap only if it is smaller than the node.
How it runs, step by step
Turn 42, 17, 8, 31, 5, 26, 12, 3, 19, 9 into a 3-ary min-heap in place. Slot i's children are slots 3 x i + 1 to 3 x i + 3, so the last slot with a child is 2. Sift each slot down from there back to the root; the leaves are heaps already.
Heapify 10 values as a 3-ary heap.
Heapify: slot 2 holds 8; its children are slots 7, 8, 9, that is 3 x 2 + 1 onward, holding 3, 19, 9. The smallest child is 3, found with 2 comparisons. 8 is larger, so they swap and the sift continues from slot 7.
Swap 8 with 3.
Heapify: slot 1 holds 17; its children are slots 4, 5, 6, that is 3 x 1 + 1 onward, holding 5, 26, 12. The smallest child is 5, found with 2 comparisons. 17 is larger, so they swap and the sift continues from slot 4.
Swap 17 with 5.
Heapify: slot 0 holds 42; its children are slots 1, 2, 3, that is 3 x 0 + 1 onward, holding 5, 3, 31. The smallest child is 3, found with 2 comparisons. 42 is larger, so they swap and the sift continues from slot 2.
Swap 42 with 3.
Heapify: slot 2 holds 42; its children are slots 7, 8, 9, that is 3 x 2 + 1 onward, holding 8, 19, 9. The smallest child is 8, found with 2 comparisons. 42 is larger, so they swap and the sift continues from slot 7.
Swap 42 with 8.
A 3-ary min-heap of height 3 with 3 on top, after 12 comparisons and 4 swaps. Bottom-up heapify is O(n) for any d: most slots are near the bottom and sift only a level or two. Compare the height with a binary heap of the same 10 values: 4.
Heap built; minimum 3.
Remember
- Children of slot i are d i + 1 to d i + d; the parent of i is (i - 1) / d.
- Wider means shallower: sift-up gets cheaper, sift-down pays d comparisons per level.
- Choose d > 2 when decrease-key or insert dominates extract-min, as in Dijkstra on dense graphs.
Topics covered
Where this is used
Graph librariesDijkstra in the Boost Graph Library
dijkstra_shortest_paths builds its queue as d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, Compare>, so the arity baked into one of the most widely used graph libraries is 4 rather than 2, and the header next to it says why: the arity has to be at least 2 and the optimal value appears to be 4 in their own and third-party experiments. The IndexInHeapMap in that type is the other half of the decision: it records each vertex's current slot, so relaxing an edge lifts that vertex in place instead of pushing a second copy. The two go together, because a wider heap only pays when the sift-ups from relaxation outnumber the sift-downs from settling, which is the shape of every Dijkstra run on a graph with more edges than vertices.
MappingOSRM road routing
OSRM's query heap is declared DAryHeap<HeapData, 4>: four children per node, an emplace that sifts up, and a decrease(handle) that also sifts up, with a reorder handler that keeps each node's stored handle correct as elements move. A continental route query relaxes far more edges than it ever settles, and the heap is large enough that each level down is a cache miss, so buying half the levels for three comparisons instead of one is the right side of the trade. It is the same arity Boost settles on, for the same workload shape.
Network optimisationLEMON's DHeap
LEMON is a C++ library for network optimisation, and lemon/dheap.h carries DHeap as the general structure with BinHeap and QuadHeap as its named D = 2 and D = 4 specialisations. Its D defaults to 16, well above what the cache argument alone would pick, and the header gives a different reason: it asks for powers of two so that the multiplications and divisions needed to walk between a node and its children run faster. The two arguments are worth keeping apart. Turning an index computation into a shift is a constant-factor win that is there at any size, while the depth argument only starts paying once the heap is large enough for a level to cost a miss. A library choosing one number for every caller lands somewhere different from a router that measured its own workload.
C++ librariesboost::heap::d_ary_heap
The container takes its arity as a template parameter, arity<4> or arity<8>, so the height-against-comparisons trade is set by the caller rather than decided by the library: more children per node means fewer levels to walk down and more children to compare at each level. It also refuses to hand out handles for decrease and increase unless it is declared mutable_<true>, and the documentation says what that costs: a mutable d_ary_heap stores its values in a std::list so the handles stay valid while elements move, which puts an indirection on every access. That is the library being explicit that in-place key updates are not free, and whether they are worth paying for is exactly the question that sets d.
Why it works this way
Why is 4 the usual pick when the comparison count says 2?
Count only comparisons and binary wins outright: the depth is ln n / ln d and each level of a sift-down spends d - 1 comparisons finding the smallest child, so extract-min costs about (d - 1) / ln d times ln n, which is 1.44 ln n at d = 2 and 2.16 ln n at d = 4 and keeps climbing. What that count ignores is where the memory is. The d children of a node sit in consecutive slots, so comparing them is one sweep across a cache line or two, while every step down the tree is a jump to a far-off address that the prefetcher cannot guess. Once the heap outgrows the cache a level costs a miss and the extra comparisons cost nothing, so fewer levels wins; the gain flattens out past the point where a node's children stop fitting in a line or two, which is why the answer in practice is 4 or 8 rather than 64.
The minus one in (i - 1) / d is not decoration
The children of i are d i + 1 through d i + d, so inverting that map has to subtract the 1 before dividing. With d = 4, slot 4 is the first child of the root: (4 - 1) / 4 gives 0, while 4 / 4 gives 1, which is one of slot 4's own siblings. The same offset sets where heapify starts, at (n - 2) / d, the parent of the last slot. The tempting generalisation n / d - 1 is not the same number: with n = 6 and d = 4 it starts at 0 and never sifts slot 1, whose only child is slot 5, so the heap comes out quietly wrong rather than crashing.
Widening only pays if you really have decrease-key
The case for d > 2 rests on cheap sift-ups outnumbering dear sift-downs, and in Dijkstra a sift-up means lowering a vertex's key where it already sits. That requires knowing where it sits: an index map from vertex to slot, rewritten on every swap, which is what Boost's d_ary_heap_indirect calls its IndexInHeapMap and what OSRM's heap calls its reorder handler. The popular shortcut of pushing a fresh (dist, v) pair and discarding stale pops gives that advantage straight back, because every extra push is eventually extracted, so each cheap sift-up buys one expensive sift-down and the heap holds up to E entries instead of V. An index map that is not updated on a swap does not crash either; it just decreases some other vertex's key.
Pick d from the graph, not from folklore
Dijkstra performs up to E decrease-keys at log_d V each and V extracts at d log_d V each, so the total is O((E + V d) log_d V), and setting d to roughly E / V balances the two terms and gives O(E log_(E/V) V). On a sparse graph where E is about V that collapses back to d = 2; on a dense one where E approaches V squared it grows with V and the bound converges on the O(V squared) scan that Dijkstra's original formulation used. That endpoint is literally the same structure: push d up to n and the heap is a root with one flat row of children, where insert is a single comparison and extract-min scans everything, which is the unsorted-array priority queue. d is a dial between those two ends, and the ratio of updates to extracts is what sets it.
Read more
- d-ary heapWikipedia
- d_ary_heap, arity and mutabilityBoost.Heap · boost.org
- Priority queues and Dijkstra's algorithmUT Austin TR-07-54 · www3.cs.stonybrook.edu
- Dijkstra with a priority queue and stale entriescp-algorithms
- Shortest Routes ICSES 1671 · cses.fi