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. A double-ended priority queue features the following operations: isEmpty() Checks if DEPQ is empty and returns true if empty. size() Returns the total number of elements present in the DEPQ. getMin() Returns the element having least priority. getMax() Returns the element having highest priority. put(x) Inserts the element x in the DEPQ. removeMin() Removes an element with minimum priority and returns this element. removeMax() Removes an element with maximum priority and returns this element. 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. 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: 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. Here, the minimum and maximum elements are values contained in the root nodes of min heap and max heap respectively. Removing the min element: Perform removemin() on the min heap and remove(node value) on the max heap, where node value is the value in the corresponding node in the max heap. Removing the max element: Perform removemax() on the max heap and remove(node value) on the min heap, where node value is the value in the corresponding node in the min heap.