# d-ary heap

Invented by Johnson (1975) a simple generalization of binary heaps $d$-ary heap is a full $d$-ary tree with a heap ordering: the priority of each node is higher then the priorities of its children root is the node with the highest priority easy implementation for small $d\geq2$ we get a more cache-efficient data structure then a binary heap large $d$'s are preferable for external data structures where the number of disk accesses should be minimized two heaps cannot be easily merged There is a trade-off between the insert and extract-min operation running in $O(\log_d n)$ and $O(d \log_d n)$, respectively. Choice $d=m/n$ leads to $O(m\log_{m/n}n)$ implementations of the Dijkstra's and Prim-Jarník algorithm.

## References

• D.B. Johnson. Priority queues with update and finding minimum spanning trees. Information Processing Letters, 4(3):53-57, 1975. [bib]