License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2022.8
URN: urn:nbn:de:0030-drops-159787
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15978/
Go to the corresponding LIPIcs Volume Portal

Brodal, Gerth Stølting

Priority Queues with Decreasing Keys

pdf-format:
LIPIcs-FUN-2022-8.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{brodal:LIPIcs.FUN.2022.8,
  author =	{Brodal, Gerth St{\o}lting},
  title =	{{Priority Queues with Decreasing Keys}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15978},
  URN =		{urn:nbn:de:0030-drops-159787},
  doi =		{10.4230/LIPIcs.FUN.2022.8},
  annote =	{Keywords: priority queue, decreasing keys, post-order heap, Dijkstra’s algorithm}
}

Keywords: priority queue, decreasing keys, post-order heap, Dijkstra’s algorithm
Collection: 11th International Conference on Fun with Algorithms (FUN 2022)
Issue Date: 2022
Date of publication: 23.05.2022
Supplementary Material: Software: https://www.cs.au.dk/~gerth/papers/fun22code.zip

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI