We introduce two data-structural transformations to construct
double-ended priority queues from priority queues. To apply our
transformations the priority queues exploited must support the
extraction of an unspecified element, in addition to the standard
priority-queue operations. With the first transformation we
obtain a double-ended priority queue which guarantees the worst-case
cost of *O*(1) for *find*-*min*, *find*-*max*, *in**sert*, *extract*;
and the worst-case cost of *O*(lg *n*) with at most lg *n* + *O*(1)
element comparisons for *delete*. With the second transformation
we get a meldable double-ended priority queue which guarantees the
worst-case cost of *O*(1) for *find*-*min*, *find*-*max*, *in**sert*,
*extract*; the worst-case cost of *O*(lg *n*) with 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. |