Two new methods for constructing double-ended priority queues from priority queues
Amr Elmasry, Claus Jensen, Jyrki Katajainen · Computing · 2008
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 , 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 find-min , find-max , 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 {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.