D-ary heap

The d-ary heap or d-heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2.[1][2][3] Thus, a binary heap is a 2-heap, and a ternary heap is a 3-heap. According to Tarjan[2] and Jensen et al.,[4] d-ary heaps were invented by Donald B. Johnson in 1975.[1]

This data structure allows decrease priority operations to be performed more quickly than binary heaps, at the expense of slower delete minimum operations. This tradeoff leads to better running times for algorithms such as Dijkstra's algorithm in which decrease priority operations are more common than delete min operations.[1][5] Additionally, d-ary heaps have better memory cache behavior than binary heaps, allowing them to run more quickly in practice despite having a theoretically larger worst-case running time.[6] Like binary heaps, d-ary heaps are an in-place data structure that use no additional storage beyond that needed to store the array of items in the heap.[2][7]

  1. ^ a b c Johnson, D. B. (1975), "Priority queues with update and finding minimum spanning trees", Information Processing Letters, 4 (3): 53–57, doi:10.1016/0020-0190(75)90001-0.
  2. ^ a b c Cite error: The named reference t83 was invoked but never defined (see the help page).
  3. ^ Cite error: The named reference w07 was invoked but never defined (see the help page).
  4. ^ Jensen, C.; Katajainen, J.; Vitale, F. (2004), An extended truth about heaps (PDF), archived from the original (PDF) on 2007-06-09, retrieved 2008-02-05.
  5. ^ Cite error: The named reference t2 was invoked but never defined (see the help page).
  6. ^ Cite error: The named reference nmm91 was invoked but never defined (see the help page).
  7. ^ Mortensen, C. W.; Pettie, S. (2005), "The complexity of implicit and space efficient priority queues", Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15–17, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3608, Springer-Verlag, pp. 49–60, doi:10.1007/11534273_6, ISBN 978-3-540-28101-6.