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 (US) |
---|---|
Pages (from-to) | 206-212 |
Number of pages | 7 |
Journal | Journal of Discrete Algorithms |
Volume | 16 |
DOIs | |
State | Published - Oct 2012 |
Keywords
- Data structures
- Distribution-sensitive structures
- Priority queues
- Splay trees
- Working-set bound
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics