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.

References

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