Improvements in double ended priority queues

In this paper, we present improved algorithms for min-max pair heaps introduced by S. Olariu et al. (A Mergeable Double-ended Priority Queue - The Comp. J. 34, 423-427, 1991). We also show that in the worst case, this structure, though slightly costlier to create, is better than min-max heaps of Strothotte (Min-max Heaps and Generalized Priority Queues - CACM, 29(10), 996-1000, Oct, 1986) in respect of deletion, and is equally good for insertion when an improved technique using binary search is applied. Experimental results show that, in the average case, with the exception of creation phase data movement, our algorithm outperforms min-max heap of Strothotte in all other aspects.

Keywords:

• Algorithm
• Heap
• Min-Max Pair Heap
• Min-Max Heap
• Priority Queues