Name
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{w"x,q"x})) time, where w"x (respectively, q"x) 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.jda.2012.04.014 | J. Discrete Algorithms |
Keywords | Field | DocType |
queueish property,last access,time-finger property,priority queue,priority-queue operation,worst-case o,corresponding operation,new unifying property,worst-case sense,worst-case constant time,priority queues,splay trees,data structures | Data structure,Discrete mathematics,Combinatorics,G/G/1 queue,Splay tree,M/G/1 queue,M/G/k queue,Priority queue,Mathematics,Double-ended priority queue | Journal |
Volume | ISSN | Citations |
16, | 1570-8667 | 2 |
PageRank | References | Authors |
0.35 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amr Elmasry | 1 | 259 | 34.53 |
| Arash Farzan | 2 | 136 | 11.07 |
| John Iacono | 3 | 404 | 42.83 |