Fast Meldable Priority Queues

Gerth Stølting Brodal

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.

Full Text:

PDF


DOI: http://dx.doi.org/10.7146/brics.v2i12.19515
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.
OK


ISSN: 0909-0878 

Hosted by the State and University Library and Aarhus University Library