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]