Name
Abstract | ||
|---|---|---|
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\{w_x, q_x\}+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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-25011-8_17 | IWOCA |
Keywords | Field | DocType |
working-set bound,queueish property,time-finger property,priority queue,asymptotically equivalent,corresponding operation,unified bound,new unifying property,worst-case sense,worst-case constant time,distribution-sensitive priority queue | Binomial options pricing model,Discrete mathematics,Combinatorics,Interleave sequence,Priority queue,Mathematics | Conference |
Volume | ISSN | Citations |
7056 | 0302-9743 | 3 |
PageRank | References | Authors |
0.40 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amr Elmasry | 1 | 259 | 34.53 |
| Arash Farzan | 2 | 136 | 11.07 |
| John Iacono | 3 | 404 | 42.83 |