Double-ended priority queue

Not to be confused with Double-ended queue.

A double-ended priority queue(DEPQ) is an abstract data type similar to a priority queue except that it allows for efficient removal of both the maximum and minimum element.It is a data structure in which one can insert elements and then remove the elements with minimum or maximum priority.Every element in a DEPQ has a priority or value.

Operations

A double-ended priority queue features the follow operations:

• isEmpty()

This function checks if DEPQ is empty and returns true if empty.

• size()

This function returns the total number of elements preset in the DEPQ.

• getMin()

This function returns the element having least priority.

• getMax()

This function returns the element having highest priority.

• put(x)

This function inserts the element 'x' in the DEPQ.

• removeMin()

This function removes an element with minimum priority and returns this element.

• removeMax()

This function removes an element with maximum priority and returns this element.

Implementation

Double-ended priority queues can be built from balanced binary search trees (where the mininum 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.

• 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.

• Leaf Correspondence: In this method only the leaf elements of the min and max PQ form corresponding pairs. It is not necessary for non-leaf elements to be in a correspondence pair.

Complexity

With implementations using heaps and pairing heaps, the operations put(x), removeMin() and removeMax() take O(log n) where n is the number of elements in the double-ended priority queue. For pairing heaps, this is an amortized complexity. The remaining DEPQ operations take O(1).

Applications

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:

• Read in as many elements as will fit into an internal DEPQ. The elements in the DEPQ will eventually be the middle group (pivot) of elements.
• Read in the remaining elements. If the next element is <= the smallest element in the DEPQ, output this next element as part of the left group. If the next element is >= the largest element in the DEPQ, output this next element as part of the right group. Otherwise, remove either the max or min element from the DEPQ (the choice may be made randomly or alternately); if the max element is removed, output it as part of the right group; otherwise, output the removed element as part of the left group; insert the newly input element into the DEPQ.
• Output the elements in the DEPQ, in sorted order, as the middle group.
• Sort the left and right groups recursively.