Fast Meldable Priority Queues
DOI:
https://doi.org/10.7146/brics.v2i12.19515Abstract
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.
Downloads
Published
1995-01-12
How to Cite
Brodal, G. S. (1995). Fast Meldable Priority Queues. BRICS Report Series, 2(12). https://doi.org/10.7146/brics.v2i12.19515
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.
