Double-ended priority queue

A double-ended priority queue, also called a DEPQ, double-ended heap or priority deque, is a data structure similar to a priority queue or heap that allows efficient removal of both the maximum and the minimum according to some ordering on the keys it stores. Every element carries a priority or value, elements can be removed in ascending as well as descending order, and the priority of an element can be changed after it has been inserted. The operations are isEmpty, size, getMin, getMax, put, removeMin and removeMax. A DEPQ can be built from balanced binary search trees, whose leftmost and rightmost leaves hold the minimum and maximum, from specialized structures such as the min-max heap, the pairing heap and the interval heap, or from two ordinary priority queues linked by the dual structure, total correspondence or leaf correspondence methods. One application is external sorting, where a DEPQ holds the middle group of elements in an external quick sort.