Priority Queues with Decreasing Keys

Author Gerth Stølting Brodal



PDF
Thumbnail PDF

File

LIPIcs.FUN.2022.8.pdf
  • Filesize: 1.08 MB
  • 19 pages

Document Identifiers

Author Details

Gerth Stølting Brodal
  • Department of Computer Science, Aarhus University, Denmark

Acknowledgements

The author wants to thank Rolf Fagerberg for insightful discussions.

Cite AsGet BibTex

Gerth Stølting Brodal. Priority Queues with Decreasing Keys. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FUN.2022.8

Abstract

A priority queue stores a set of items with associated keys and supports the insertion of a new item and extraction of an item with minimum key. In applications like Dijkstra’s single source shortest path algorithm and Prim-Jarník’s minimum spanning tree algorithm, the key of an item can decrease over time. Usually this is handled by either using a priority queue supporting the deletion of an arbitrary item or a dedicated DecreaseKey operation, or by inserting the same item multiple times but with decreasing keys. In this paper we study what happens if the keys associated with items in a priority queue can decrease over time without informing the priority queue, and how such a priority queue can be used in Dijkstra’s algorithm. We show that binary heaps with bottom-up insertions fail to report items with unchanged keys in correct order, while binary heaps with top-down insertions report items with unchanged keys in correct order. Furthermore, we show that skew heaps, leftist heaps, and priority queues based on linking roots of heap-ordered trees, like pairing heaps, binomial queues and Fibonacci heaps, work correctly with decreasing keys without any modifications. Finally, we show that the post-order heap by Harvey and Zatloukal, a variant of a binary heap with amortized constant time insertions and amortized logarithmic time deletions, works correctly with decreasing keys and is a strong contender for an implicit priority queue supporting decreasing keys in practice.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • priority queue
  • decreasing keys
  • post-order heap
  • Dijkstra’s algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Gerth Stølting Brodal. A survey on priority queues. In Andrej Brodnik, Alejandro López-Ortiz, Venkatesh Raman, and Alfredo Viola, editors, Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, volume 8066 of Lecture Notes in Computer Science, pages 150-163. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40273-9_11.
  2. Svante Carlsson, J. Ian Munro, and Patricio V. Poblete. An implicit binomial queue with constant insertion time. In Rolf G. Karlsson and Andrzej Lingas, editors, SWAT 88, 1st Scandinavian Workshop on Algorithm Theory, Halmstad, Sweden, July 5-8, 1988, Proceedings, volume 318 of Lecture Notes in Computer Science, pages 1-13. Springer, 1988. URL: https://doi.org/10.1007/3-540-19487-8_1.
  3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  4. Clark A. Crane. Linear Lists and Priority Queues as Balanced Binary Trees. PhD thesis, Department of Computer Science, Stanford University, 1972. Google Scholar
  5. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959. URL: https://doi.org/10.1007/BF01386390.
  6. James R. Driscoll, Harold N. Gabow, Ruth Shrairman, and Robert Endre Tarjan. Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Commun. ACM, 31(11):1343-1354, 1988. URL: https://doi.org/10.1145/50087.50096.
  7. Amr Elmasry, Claus Jensen, and Jyrki Katajainen. Two skew-binary numeral systems and one application. Theory Comput. Syst., 50(1):185-211, 2012. URL: https://doi.org/10.1007/s00224-011-9357-0.
  8. Michael L. Fredman, Robert Sedgewick, Daniel Dominic Sleator, and Robert Endre Tarjan. The pairing heap: A new form of self-adjusting heap. Algorithmica, 1(1):111-129, 1986. URL: https://doi.org/10.1007/BF01840439.
  9. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596-615, 1987. URL: https://doi.org/10.1145/28869.28874.
  10. Nicholas J. A. Harvey and Kevin C. Zatloukal. The post-order heap. In Proceedings Third International Conference on Fun with Algorithms (FUN 2004), 2004. URL: http://people.csail.mit.edu/nickh/Publications/PostOrderHeap/FUN04-PostOrderHeap.pdf.
  11. Vojtěch Jarník. O jistém problem minimálním. Práce Moravské Pridovedecké Spolecnosti v Brně, 4:57-63, 1930. Google Scholar
  12. Irit Katriel and Ulrich Meyer. Elementary graph algorithms in external memory. In Ulrich Meyer, Peter Sanders, and Jop F. Sibeyn, editors, Algorithms for Memory Hierarchies, Advanced Lectures, volume 2625 of Lecture Notes in Computer Science, pages 62-84. Springer, 2002. URL: https://doi.org/10.1007/3-540-36574-5_4.
  13. Anthony LaMarca and Richard E. Ladner. The influence of caches on the performance of heaps. ACM J. Exp. Algorithmics, 1:4, 1996. URL: https://doi.org/10.1145/235141.235145.
  14. Eugene W. Myers. An applicative random-access stack. Inf. Process. Lett., 17(5):241-248, 1983. URL: https://doi.org/10.1016/0020-0190(83)90106-0.
  15. Thomas Porter and István Simon. Random insertion into a priority queue structure. IEEE Trans. Software Eng., 1(3):292-298, 1975. URL: https://doi.org/10.1109/TSE.1975.6312854.
  16. R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6):1389-1401, 1957. URL: https://doi.org/10.1002/j.1538-7305.1957.tb01515.x.
  17. Peter Sanders. Fast priority queues for cached memory. ACM J. Exp. Algorithmics, 5:7, 2000. URL: https://doi.org/10.1145/351827.384249.
  18. Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting heaps. SIAM J. Comput., 15(1):52-69, 1986. URL: https://doi.org/10.1137/0215004.
  19. Jean Vuillemin. A data structure for manipulating priority queues. Commun. ACM, 21(4):309-315, 1978. URL: https://doi.org/10.1145/359460.359478.
  20. J. W. J. Williams. Algorithm 232 heapsort. Commun. ACM, 7(6):347-348, 1964. URL: https://doi.org/10.1145/512274.512284.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail