A priority queue with the time-finger property

Amr Ahmed Abd Elmoneim Elmasry; Arash Farzan; John Iacono

doi:10.1016/j.jda.2012.04.014

A priority queue with the time-finger property

Amr Ahmed Abd Elmoneim Elmasry, Arash Farzan, John Iacono

Department of Computer Science

3 Citations (Scopus)

Abstract

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.

Original language	English
Journal	Journal of Discrete Algorithms
Volume	16
Pages (from-to)	206-212
Number of pages	7
ISSN	1570-8667
DOIs	https://doi.org/10.1016/j.jda.2012.04.014
Publication status	Published - Oct 2012
Event	22nd International Workshop on Combinatorial Algorithms - University of Victoria, Victoria, Canada Duration: 20 Jun 2011 → 22 Jun 2011 Conference number: 22

Conference

Conference	22nd International Workshop on Combinatorial Algorithms
Number	22
Location	University of Victoria
Country/Territory	Canada
City	Victoria
Period	20/06/2011 → 22/06/2011

Access to Document

10.1016/j.jda.2012.04.014

elsevier_309878.pdfFinal published version, 224 KB

Cite this

@inproceedings{fbfeb1b7c8d64f2bba83e0f71b581f9c,

title = "A priority queue with the time-finger property",

abstract = "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.",

author = "Elmasry, {Amr Ahmed Abd Elmoneim} and Arash Farzan and John Iacono",

year = "2012",

month = oct,

doi = "10.1016/j.jda.2012.04.014",

language = "English",

volume = "16",

pages = "206--212",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press",

note = "22nd International Workshop on Combinatorial Algorithms, IWOCA 2011 ; Conference date: 20-06-2011 Through 22-06-2011",

}

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 -

A priority queue with the time-finger property

Abstract

Conference

Access to Document

Fingerprint

Cite this