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