TY - CHAP

T1 - Melding priority queues

AU - Mendelson, Ran

AU - Tarjan, Robert E.

AU - Thorup, Mikkel

AU - Zwick, Uri

PY - 2004/1/1

Y1 - 2004/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33746062908&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33746062908&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-27810-8_20

DO - 10.1007/978-3-540-27810-8_20

M3 - Chapter

AN - SCOPUS:33746062908

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 223

EP - 235

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Hagerup, Torben

A2 - Katajainen, Jyrki

PB - Springer Verlag

ER -