Item

Abstract

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 \Findmin{}, \Findmax{}, \Insert{}, \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 \Findmin{}, \Findmax{}, \Insert{}, \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\set{\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.