Fast Meldable Priority Queues

Gerth Stølting Brodal

In Proc. 4th International Workshop on Algorithms and Data Structures, volume 955 of Lecture Notes in Computer Science, pages 282-290. Springer Verlag, Berlin, 1995.

Abstract

We present priority queues that support the operations FindMin, Insert, MakeQueue 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

© Springer-Verlag Berlin Heidelberg 1995. All rights reserved.

Online version

wads95.pdf (170 Kb)

DOI

10.1007/3-540-60220-8_70

Slides

wads95.pdf (155 Kb)

BIBTEX entry

@incollection{wads95,
  author = "Gerth St{\o}lting Brodal",
  booktitle = "Proc. 4th International Workshop on Algorithms and Data Structures",
  doi = "10.1007/3-540-60220-8_70",
  isbn = "978-3-540-60220-0",
  pages = "282-290",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Fast Meldable Priority Queues",
  volume = "955",
  year = "1995"
}

Other versions