Double-ended priority queue

Not to be confused with Double-ended queue.

In computer science, a double-ended priority queue (DEPQ)[1] or double-ended heap[2] 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.[3]

  1. ^ Data Structures, Algorithms, & Applications in Java: Double-Ended Priority Queues, Sartaj Sahni, 1999.
  2. ^ Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. p. 211. ISBN 9780521880374.
  3. ^ "Depq - Double-Ended Priority Queue". Archived from the original on 2012-04-25. Retrieved 2011-10-04.