The authors describe three general correspondence methods--total, dual, and leaf--that can be used to derive efficient double-ended priority queues from single-ended priority queues. The methods are shown by developing double-ended priority queues based on the classical heap. Experimental results show that the leaf correspondence method generally produces a faster double-ended priority queue than the total or dual correspondence methods. On randomly generated data, the splay tree is faster than the tested correspondence-based double-ended priority queues.

The paper is written in six sections. The first section, the introduction, defines a min priority queue, a max priority queue, a meldable priority queue, and a double-ended (min/max) priority queue. Section 2 reviews a simple method for building a meldable double-ended priority queue from a meldable priority queue; this method creates the dual priority queue. Section 3 describes the total correspondence method, and section 4 describes the leaf-correspondence method. Section 5 gives complexity results.

In section 6, the authors present the results of experiments that compare the performance of the meldable double-ended priority queue, based on height-biased leftist trees, pairing heaps, and fast meldable priority queues. The data for splay trees are also provided.

The paper is well written. The authors describe in detail the priority queue and double-ended priority queue structures, and both theoretical and experimental results.

The set of references is comprehensive and appears complete. The paper is a good exposition of three very interesting approaches to double-ended priority queues. It is accessible to those who know some computer science.