A priority queue which simultaneously keeps track of the maximum and minimum keys, and supports operations efficiently on either extreme (minimum or maximum).