# d-ary heap

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. |

[You can download the application for offline viewing.]

## References

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