d-ary heap: more children, shallower tree, more compares

The idea: give each node more children

A binary heap is a complete tree stored in an array, where every node has at most 2 children and no child is smaller than its parent. A d-ary heap is the same thing with up to d children per node. The page runs the same operations on a binary heap (left) and a d-ary heap (right, d = 4 unless you pick 3 or 8) and counts the work. One step on the canvas is one level in each heap, so the shallower heap finishes first and shows ✓.

Nothing else changes. There are still no pointers: the children of slot i are slots d·i + 1 to d·i + d, and its parent is slot ⌊(i − 1) / d⌋. A tree of n keys has about log_d n levels: 21 keys need 5 levels with d = 2 but only 3 with d = 4.

Sift-up gets cheaper

Insert writes the key into the next free slot and sifts it up: compare with the parent, swap while smaller. Decrease-key lowers a key in place and sifts it up the same way. Each level costs one compare, so fewer levels means less work, and the gain grows with d.

• Demo: insert 21 keys: the binary heap does 31 compares and 13 swaps, the 4-ary heap 25 compares and 7 swaps.
• Demo: decrease-key burst lowers four keys on the bottom level to new minimums: 13 compares and 11 swaps against 6 and 4.

Sift-down: fewer levels, more compares per level

Extract-min takes the root, moves the last key there and sifts it down. At every level it must find the smallest of up to d children (d − 1 compares) and then compare that child with the key (1 more). So each level costs about d compares, and a whole sift-down about d · log_d n.

The extra compares per level and the saved levels cancel out for small d: d / ln d is smallest at d = 3 and almost the same at 2 and 4. Past that, the compares win. On the page, four extract-mins cost 27 compares in the binary heap, 27 with d = 3, 26 with d = 4 and 40 with d = 8 (Demo: extract-min ×4, Demo: d = 8, extract-min ×4). Swaps keep falling (13, 9, 7, 5) because swaps are paid per level.

operation	levels walked	compares	swaps
insert, decrease-key (sift-up)	≤ logd n	1 per level	≤ 1 per level
extract-min (sift-down)	≤ logd n	d per level	≤ 1 per level
find-min	0	0	0

Why 4-ary heaps are common

• Dijkstra and A* do one extract-min per vertex but can do one decrease-key per edge. With many more edges than vertices, making decrease-key cheaper pays off, and a heap with d ≈ edges / vertices gives Dijkstra O(m log_m/n n) time. See Dijkstra's Shortest Path and Binary vs Fibonacci Heap.
• Timer queues (event loops, schedulers) insert and cancel far more timers than ever fire. Go's runtime keeps its timers in a 4-ary heap, and .NET's PriorityQueue is a 4-ary heap too.
• Memory: the 4 children of a node sit next to each other in the array, usually in one cache line. Finding the smallest of them costs 3 compares but only one cache miss, so a 4-ary heap is often faster than a binary heap even on extract-min, though the compare counts are the same.

See also Priority Queues (binary heap) and Heap Sort, which works with any d too.

An indexed heap adds the position map that decrease-key needs to find a key before sifting it up.

What the page leaves out

The heaps hold at most 21 distinct keys, and the page counts compares and swaps rather than measuring time, so cache effects are only described above. It leaves out building a d-ary heap in O(n) with bottom-up heapify, delete of an arbitrary key, the "hole" trick that moves keys instead of swapping them, d-ary heaps laid out so each node's children fill exactly one cache line, and the other heap shapes (leftist, skew, binomial, Fibonacci, pairing) that make merging two heaps cheap.

References

d-ary heap (Wikipedia)

Johnson, "Priority queues with update and finding minimum spanning trees", Information Processing Letters 1975

Go runtime timers, a 4-ary heap (time.go)