Double-ended priority queue

In computer science, a double-ended priority queue (DEPQ) or double-ended heap is a data structure similar to a priority queue or heap, but allows for efficient removal of both the maximum and minimum, according to some ordering on the "keys" (items) stored in the structure. Every element in a DEPQ has a priority or value. In a DEPQ, it is possible to remove the elements in both ascending as well as descending order.
Operations.
A double-ended priority queue features the following operations:
If an operation is to be performed on two elements having the same priority, then the element inserted first is chosen. Also, the priority of any element can be changed once it has been inserted in the DEPQ.
Implementation.
Double-ended priority queues can be built from balanced binary search trees (where the minimum and maximum elements are the leftmost and rightmost leaves, respectively), or using specialized data structures like min-max heap and pairing heap.
Generic methods of arriving at double-ended priority queues from normal priority queues are:
Dual structure method.
In this method two different priority queues for min and max are maintained. The same elements in both the PQs are shown with the help of correspondence pointers.<br>
Here, the minimum and maximum elements are values contained in the root nodes of min heap and max heap respectively.
Total correspondence.
Half the elements are in the min PQ and the other half in the max PQ. Each element in the min PQ has a one-to-one correspondence with an element in max PQ. If the number of elements in the DEPQ is odd, one of the elements is retained in a buffer. Priority of every element in the min PQ will be less than or equal to the corresponding element in the max PQ.<br>
Leaf correspondence.
In this method only the leaf elements of the min and max PQ form corresponding one-to-one pairs. It is not necessary for non-leaf elements to be in a one-to-one correspondence pair.<br>
Interval heaps.
Apart from the above-mentioned correspondence methods, DEPQ's can be obtained efficiently using interval heaps. An interval heap is like an embedded min-max heap in which each node contains two elements. It is a complete binary tree in which:
Depending on the number of elements, two cases are possible - 
Inserting an element.
Depending on the number of elements already present in the interval heap, following cases are possible:
The time required for inserting an element depends on the number of movements required to meet all the conditions and is O(log "n").
Deleting an element.
Thus, with interval heaps, both the minimum and maximum elements can be removed efficiently traversing from root to leaf. Thus, a DEPQ can be obtained from an interval heap where the elements of the interval heap are the priorities of elements in the DEPQ.
Time Complexity.
Interval Heaps.
When DEPQ's are implemented using Interval heaps consisting of "n" elements, the time complexities for the various functions are formulated in the table below
Pairing heaps.
When DEPQ's are implemented using heaps or pairing heaps consisting of "n" elements, the time complexities for the various functions are formulated in the table below. For pairing heaps, it is an amortized complexity.
Applications.
External sorting.
One example application of the double-ended priority queue is external sorting. In an external sort, there are more elements than can be held in the computer's memory. The elements to be sorted are initially on a disk and the sorted sequence is to be left on the disk. The external quick sort is implemented using the DEPQ as follows: