Randomized Meldable Priority Queues
by Anna Gambin and Adam Malinowski

Abstract:

We present a practical meldable priority queue
implementation.  All priority queue operations are very
simple and their logarithmic time bound holds with high
probability, which makes this data structure more suitable
for real-time applications than those with only amortized
performance guarantees.  Our solution is also
space-efficient, since it does not require storing any
auxiliary information within the queue nodes.