Aarhus University Seal

Priority Queues with Decreasing Keys

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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.

Original languageEnglish
Title of host publication11th International Conference on Fun with Algorithms, FUN 2022
EditorsPierre Fraigniaud, Yushi Uno
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication yearMay 2022
ISBN (Electronic)9783959772327
Publication statusPublished - May 2022
Event11th International Conference on Fun with Algorithms, FUN 2022 - Sicily, Italy
Duration: 30 May 20223 Jun 2022


Conference11th International Conference on Fun with Algorithms, FUN 2022
SeriesLeibniz International Proceedings in Informatics, LIPIcs

Bibliographical note

Publisher Copyright:
© Gerth Stølting Brodal.

    Research areas

  • decreasing keys, Dijkstra's algorithm, post-order heap, Priority queue

See relations at Aarhus University Citationformats

ID: 271961644