208. What is a d-ary heap, how is it indexed, and when is it better than a binary heap?
MediumPriority queues & heaps
Technical
Show model answer
Each node has up to d children. In a 0-based array, the children of i are d·i + 1 through d·i + d and the parent of i is floor((i − 1) / d). The height is about log_d n.
Insert and decrease-key only sift up, costing O(log_d n), which is cheaper than binary. Delete-min sifts down and compares d children per level, costing O(d log_d n), which is more expensive. So larger d suits workloads with many decrease-keys, like Dijkstra on dense graphs (d ≈ E/V gives O(E log_{E/V} V)), and 4-ary heaps are often faster in practice thanks to better cache locality.