Worst case constant time priority queue
Andrej Brodnik, Svante Carlsson, Johan Karlsson et al. · 2001
We present a new data structure of size O(M) for solving the vEB problem. When this data structure is used in combination with a new memory topology it provides an O(1) worst case time solution. 1
Cited by 15 works. doi:10.5555/365411.365524
Authors
References
- Design and implementation of an efficient priority queue
- Should Tables Be Sorted?
- Log-logarithmic worst-case range queries are possible in space Θ(N)
- The cell probe complexity of dynamic data structures
- A Lower Bound on the Complexity of the Union-Split-Find Problem
- Machine Models and Simulation.
- Optimal bounds for the predecessor problem
- Lower bounds for union-split-find related problems on random access machines
- Tight(er) worst-case bounds on dynamic searching and priority queues
- Searching in constant time and minimum space