Fast Meldable Priority Queues

Gerth Stølting Brodal

Technical Report, BRICS-RS-95-12, BRICS, Department of Computer Science, Aarhus University, 12 pages, February 1995.

Abstract

We present priority queues that support the operations MakeQueue, FindMin, Insert and Meld in worst case time O(1) and Delete and DeleteMin in worst case time O(log n). They can be implemented on the pointer machine and require linear space. The time bounds are optimal for all implementations where Meld takes worst case time o(n).

To our knowledge this is the first priority queue implementation that supports Meld in worst case constant time and DeleteMin in logarithmic time.

Copyright notice

Copyright © 1995, BRICS, Department of Computer Science, Aarhus University. All rights reserved.

Online version

brics-rs-95-12.pdf (200 Kb)

Note

Appears in the proceedings of WADS'95

BIBT_EX entry

@techreport{brics-rs-95-12,
  author = "Gerth Stølting Brodal",
  institution = "BRICS, Department of Computer Science, Aarhus University",
  issn = "0909-0878",
  month = "February",
  number = "BRICS-RS-95-12",
  pages = "12",
  title = "Fast Meldable Priority Queues",
  year = "1995"
}