### 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 language | English (US) |
---|---|

Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Editors | Torben Hagerup, Jyrki Katajainen |

Publisher | Springer Verlag |

Pages | 223-235 |

Number of pages | 13 |

ISBN (Electronic) | 3540223398, 9783540223399 |

DOIs | |

State | Published - Jan 1 2004 |

### Publication series

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

Volume | 3111 |

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

*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