2026-08-16T15:14:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15978 2024-03-06T10:56:59Z ddc:004 open_access

Priority Queues with Decreasing Keys Brodal, Gerth Stølting priority queue decreasing keys post-order heap Dijkstra’s algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gerth Stølting Brodal 2022 Is Part Of LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2022.8 urn:nbn:de:0030-drops-159787 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.8 eng https://creativecommons.org/licenses/by/4.0/legalcode