TY - JOUR

T1 - Two new methods for constructing double-ended priority queues from priority queues

AU - Elmasry, Amr

AU - Jensen, Claus

AU - Katajainen, Jyrki

PY - 2008

Y1 - 2008

N2 - 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 unspecifiedelement, 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 {lgm, lg n}) for meld. Here, m and n denote the number of elements stored in the data structures prior to the operation in question.

AB - 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 unspecifiedelement, 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 {lgm, lg n}) for meld. Here, m and n denote the number of elements stored in the data structures prior to the operation in question.

U2 - 10.1007/s00607-008-0019-2

DO - 10.1007/s00607-008-0019-2

M3 - Journal article

VL - 83

SP - 193

EP - 204

JO - Computing (Vienna/New York)

JF - Computing (Vienna/New York)

SN - 0010-485X

IS - 4

ER -