MERGEABLE DOUBLE-ENDED PRIORITY QUEUES
Seonghun Cho, Sartaj K. Sahni · International Journal of Foundations of Computer Science · 1999
We show that the leftist tree data structure may be adapted to obtain data structures that permit the double-ended priority queue operations Insert, DeleteMin, DeleteMax, and Merge to be done in O( log n) time where n is the size of the resulting queue. The operations FindMin and FindMax can be done in O(1) time. Experimental results are also presented.