ABSTRACT
A double-ended priority queue (DEPQ) is a collection of zero or more elements. Each element has a priority or value. The operations performed on a double-ended priority queue are:
1. getMin() ... return element with minimum priority 2. getMax() ... return element with maximum priority 3. put(x) ... insert the element x into the DEPQ 4. removeMin() ... remove an element with minimum priority and return this
element 5. removeMax() ... remove an element with maximum priority and return this
element
One application of a DEPQ is to the adaptation of quick sort, which has the the best expected run time of all known internal sorting methods, to external sorting. The basic idea in quick sort is to partition the elements to be sorted into three groups L, M , and R. The middle group M contains a single element called the pivot, all elements in the left group L are ≤ the pivot, and all elements in the right group R are ≥ the pivot. Following this partitioning, the left and right element groups are sorted recursively.
