A unifying property for distribution-sensitive priority queues

TY - GEN

T1 - A unifying property for distribution-sensitive priority queues

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Farzan, Arash

AU - Iacono, John

N1 - Conference code: 22

PY - 2011

Y1 - 2011

N2 - We present a priority queue that supports the operations: insert in worst-case constant time, and delete, delete-min, find-min and decrease-key on an element x in worst-case O(lg(min{wx, qx} + 2)) time, where wx (respectively, qx) is the number of elements that were accessed after (respectively, before) the last access of x and are still in the priority queue at the time when the corresponding operation is performed. Our priority queue then has both the working-set and the queueish properties; and, more strongly, it satisfies these properties in the worst-case sense. We also argue that these bounds are the best possible with respect to the considered measures. Moreover, we modify our priority queue to satisfy a new unifying property - the time-finger property - which encapsulates both the working-set and the queueish properties. In addition, we prove that the working-set bound is asymptotically equivalent to the unified bound (which is the minimum per operation among the static-finger, static-optimality, and working-set bounds). This latter result is of tremendous interest by itself as it had gone unnoticed since the introduction of such bounds by Sleater and Tarjan [10]. Together, these results indicate that our priority queue also satisfies the static-finger, the static-optimality and the unified bounds.

AB - We present a priority queue that supports the operations: insert in worst-case constant time, and delete, delete-min, find-min and decrease-key on an element x in worst-case O(lg(min{wx, qx} + 2)) time, where wx (respectively, qx) is the number of elements that were accessed after (respectively, before) the last access of x and are still in the priority queue at the time when the corresponding operation is performed. Our priority queue then has both the working-set and the queueish properties; and, more strongly, it satisfies these properties in the worst-case sense. We also argue that these bounds are the best possible with respect to the considered measures. Moreover, we modify our priority queue to satisfy a new unifying property - the time-finger property - which encapsulates both the working-set and the queueish properties. In addition, we prove that the working-set bound is asymptotically equivalent to the unified bound (which is the minimum per operation among the static-finger, static-optimality, and working-set bounds). This latter result is of tremendous interest by itself as it had gone unnoticed since the introduction of such bounds by Sleater and Tarjan [10]. Together, these results indicate that our priority queue also satisfies the static-finger, the static-optimality and the unified bounds.

UR - http://www.scopus.com/inward/record.url?scp=81855228593&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-25011-8_17

DO - 10.1007/978-3-642-25011-8_17

M3 - Article in proceedings

AN - SCOPUS:81855228593

SN - 978-3-642-25010-1

T3 - Lecture notes in computer science

SP - 209

EP - 222

BT - Combinatorial Algorithms

A2 - Iliopoulos, Costas S.

A2 - Smyth, William F.

PB - Springer

T2 - 22nd International Workshop on Combinatorial Algorithms

Y2 - 20 June 2011 through 22 June 2011

ER -