Two new ways of transforming a priority queue into a double-ended priority queue are introduced. These methods can be used to improve all known bounds for the comparison complexity of double-ended priority-queue operations. Using an efficient priority queue, the first transformation can produce a double-ended priority queue which guarantees the worst-case cost of O(1) for find-min, find-max, and insert; and the worst-case cost of O(lg n) including at most lg n + O(1) element comparisons for delete, but the data structure cannot support meld efficiently. Using a meldable priority queue that supports decrease efficiently, the second transformation can produce a meldable double-ended priority queue which guarantees the worst-case cost of O(1) for find-min, find-max, and insert; the worst-case cost of O(lg n) including at most lg n + O(lg lg n) element comparisons for delete; and the worst-case cost of O(min{lg m, lg n}) for meld. Here, m and n denote the number of elements stored in the data structures prior to the operation in question, and lg n is a shorthand for log₂(max{2, n}).

@report{EJK2006dR,
  author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
  title = {Two new methods for transforming priority queues into double-ended
    priority queues},
  type = {CPH STL Report},
  number = {2006-9},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {2006},
  pagetotal = {14},
}