Worst-case optimal priority queues via extended regular counters

TY - GEN

T1 - Worst-case optimal priority queues via extended regular counters

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Katajainen, Jyrki

N1 - Conference code: 7

PY - 2012

Y1 - 2012

N2 - We consider the classical problem of representing a collection of priority queues under the operations find-min, insert, decrease, meld, delete, and delete-min. In the comparison-based model, if the first four operations are to be supported in constant time, the last two operations must take at least logarithmic time. Brodal showed that his worst-case efficient priority queues achieve these worst-case bounds. Unfortunately, this data structure is involved and the time bounds hide large constants. We describe a new variant of the worst-case efficient priority queues that relies on extended regular counters and provides the same asymptotic time and space bounds as the original. Due to the conceptual separation of the operations on regular counters and all other operations, our data structure is simpler and easier to describe and understand. Also, the constants in the time and space bounds are smaller.

AB - We consider the classical problem of representing a collection of priority queues under the operations find-min, insert, decrease, meld, delete, and delete-min. In the comparison-based model, if the first four operations are to be supported in constant time, the last two operations must take at least logarithmic time. Brodal showed that his worst-case efficient priority queues achieve these worst-case bounds. Unfortunately, this data structure is involved and the time bounds hide large constants. We describe a new variant of the worst-case efficient priority queues that relies on extended regular counters and provides the same asymptotic time and space bounds as the original. Due to the conceptual separation of the operations on regular counters and all other operations, our data structure is simpler and easier to describe and understand. Also, the constants in the time and space bounds are smaller.

U2 - 10.1007/978-3-642-30642-6_13

DO - 10.1007/978-3-642-30642-6_13

M3 - Article in proceedings

SN - 978-3-642-30641-9

T3 - Lecture notes in computer science

SP - 125

EP - 137

BT - Computer Science – Theory and Applications

A2 - Hirsch, Edward A.

A2 - Karhumäki, Juhani

A2 - Lepistö, Arto

A2 - Prilutskii, Michail

PB - Springer

T2 - The 7th International Computer Science Symposium in Russia

Y2 - 3 July 2012 through 7 July 2012

ER -