Melding priority queues

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

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

We show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) amortized time, where n is an upper bound on the number of elements in the priority queue, can be converted into a priority queue data structure that also supports fast meld operations with essentially no increase in the amortized cost of the other operations. 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) + a(n)) amortized time, where a(n) is a functional inverse of the Ackermann function, and where n this time is the total number of operations performed on all the priority queues. The construction is very simple. The meldable priority queues are obtained by placing a nonmeldable priority queue at each node of a union-find data structure.We also show that when all keys are integers in the range [1, N], we can replace n in the bound stated previously by min{n, N}. Applying this result to the nonmeldable priority queue data structures obtained recently by Thorup [2002b] and by Han and Thorup [2002] we obtain meldable RAM priority queues with O(log log n)amortized time per operation, or O(vlog log n) expected amortized time per operation, respectively. As a by-product, we obtain improved algorithms for the minimum directed spanning tree problem on graphs with integer edge weights, namely, a deterministic O(m log log n)-time algorithm and a randomized O(mvlog log n)-time algorithm. For sparse enough graphs, these bounds improve on the O(m + n log n) running time of an algorithm by Gabow et al. [1986] that works for arbitrary edge weights.

Original languageEnglish (US)
Pages (from-to)535-556
Number of pages22
JournalACM Transactions on Algorithms
Volume2
Issue number4
DOIs
StatePublished - Oct 1 2006

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

Keywords

  • Disjoint set union
  • Heaps
  • Minimum directed spanning trees
  • Optimum branchings
  • Priority queues
  • Union-find
  • Word RAM model

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

  • Cite this