Fast Meldable Priority Queues

Gerth Stølting Brodal

February 1995


We present priority queues that support the operations MAKEQUEUE, FINDMIN, INSERT and MELD in worst case time tex2html_wrap_inline27 and DELETE and DELETEMIN in worst case time tex2html_wrap_inline29. 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 tex2html_wrap_inline31.

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

Available as PostScript, PDF.


Last modified: 2003-06-08 by webmaster.