A priority queue with the time-finger property

TY - GEN

T1 - A priority queue with the time-finger property

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Farzan, Arash

AU - Iacono, John

N1 - Conference code: 22

PY - 2012/10

Y1 - 2012/10

N2 - We present a priority queue that supports insert in worst-case constant time, and delete-min, access-min, delete, and decrease of an element x in worst-case O(log(min{wx,qx})) time, where wx (respectively, qx) is the number of elements that were accessed after (respectively, before) the last access to x and are still in the priority queue at the time when the corresponding operation is performed. (An access to an element is accounted for by any priority-queue operation that involves this element.) 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. From the results in Iacono (2001) [11] and Elmasry et al. (2011) [7], our priority queue also satisfies the static-finger, static-optimality, and unified bounds. Moreover, we modify our priority queue to realize a new unifying property - the time-finger property - which encapsulates both the working-set and the queueish properties.

AB - We present a priority queue that supports insert in worst-case constant time, and delete-min, access-min, delete, and decrease of an element x in worst-case O(log(min{wx,qx})) time, where wx (respectively, qx) is the number of elements that were accessed after (respectively, before) the last access to x and are still in the priority queue at the time when the corresponding operation is performed. (An access to an element is accounted for by any priority-queue operation that involves this element.) 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. From the results in Iacono (2001) [11] and Elmasry et al. (2011) [7], our priority queue also satisfies the static-finger, static-optimality, and unified bounds. Moreover, we modify our priority queue to realize a new unifying property - the time-finger property - which encapsulates both the working-set and the queueish properties.

U2 - 10.1016/j.jda.2012.04.014

DO - 10.1016/j.jda.2012.04.014

M3 - Conference article

SN - 0196-6774

VL - 16

SP - 206

EP - 212

JO - Journal of Algorithms

JF - Journal of Algorithms

T2 - 22nd International Workshop on Combinatorial Algorithms

Y2 - 20 June 2011 through 22 June 2011

ER -