| Invented by | Johnson (1975) | |
| Idea: |
- 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
|
| Advantages: |
- 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
|
| Disadvantages: | two heaps cannot be easily merged |
| Note: | 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. |