# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Two New Methods for Constructing Double-ended Priority Queues from Priority Queues

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Elmasry, A. (2008). Two New Methods for Constructing Double-ended Priority Queues from
Priority Queues.* Computing,* *83*(4), 193-204. doi:10.1007/s00607-008-0019-2.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1D4F-8

##### 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.