Melding priority queues

Ran Mendelson, Robert E. Tarjan, Mikkel Thorup, Uri Zwick

Research output: Chapter in Book/Report/Conference proceedingChapter

5 Scopus citations

Abstract

We show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) time, when there are up to n elements in the priority queue, can be converted into a priority queue data structure that also supports meld operations at essentially no extra cost, at least in the amortized sense. More specifically, the new data structure supports insert, meld and find-min operations in O(1) amortized time, and delete operations in O(pq(n)α(n, n/pq(n))) amortized time, where α(m, n) is a functional inverse of the Ackermann function. For all conceivable values of pq(n), the term α(n, n/pq(n)) is constant. This holds, for example, if pq(n) = Ω(log* n). In such cases, adding the meld operation does not increase the amortized asymptotic cost of the priority queue operations. The result is obtained by an improved analysis of a construction suggested recently by three of the authors in [14]. The construction places a non-meldable priority queue at each node of a union-find data structure. We also show that when all keys are integers in [1, N], we can replace n in all the bounds stated above by N.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsTorben Hagerup, Jyrki Katajainen
PublisherSpringer Verlag
Pages223-235
Number of pages13
ISBN (Electronic)3540223398, 9783540223399
DOIs
StatePublished - Jan 1 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3111
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Melding priority queues'. Together they form a unique fingerprint.

  • Cite this

    Mendelson, R., Tarjan, R. E., Thorup, M., & Zwick, U. (2004). Melding priority queues. In T. Hagerup, & J. Katajainen (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 223-235). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3111). Springer Verlag. https://doi.org/10.1007/978-3-540-27810-8_20