Bounded ordered dictionaries in O(log log N) time and O(n) space. (English) Zbl 0702.68042

Summary: We show how to implement bounded ordered dictionaries, also called bounded priority queues, in O(log log N) time per operation and O(n) space. Here n denotes the number of elements stored in the dictionary and N denotes the size of the universe. Previously, this time bound required O(N) space.


68P05 Data structures
68Q25 Analysis of algorithms and problem complexity


Full Text: DOI


[1] Dietzfelbinger, M.; Karlin, A.; Mehlhorn, K.; auf der Heide, F. Meyer; Rohnert, H.; Tarjan, R., Upper and lower bounds for the dictionary problem, Proc. 29th IEEE Symposium on Foundations of Computer Science (1988) · Zbl 0651.68095
[2] Fredman, M. L.; Komlos, J.; Szemeredi, E., Storing a sparse table with O(1) worst case access time, J. ACM, 31, 3, 538-544 (1984) · Zbl 0629.68068
[3] Johnson, D., A priority queue in which initialization and queue operations take time O(log log \(D)\) time, Math. System Theory, 15, 295-309 (1982) · Zbl 0522.68039
[4] Karlsson, R. G., Algorithms in a restricted universe, Rept. CS-84-50 (1984), Department of Computer Science, University of Waterloo: Department of Computer Science, University of Waterloo Waterloo, Ont
[5] Mehlhorn, K., Data Structures and Algorithms I (1984), Springer: Springer Berlin
[6] Mehlhorn, K.; Näher, St., LEDA, a library of efficient data types and algorithms, Proc. MFCS ’89, 88-106 (1989)
[7] Emde Boas, P.van, An \(O(n\) log log \(n)\) on-line algorithm for the insert-extract-min problem, Rept. 74 (1974), Department of Computer Science, Cornell University: Department of Computer Science, Cornell University Ithaca, NY
[8] Emde Boas, P.van, Preserving order in a forest in less than logarithmic time and linear space, Inform. Process. Lett., 6, 80-82 (1977) · Zbl 0364.68053
[9] Emde Boas, P.van; Kaas, R.; Zijlstra, E., Design and implementation of an efficient priority queue, Math. Systems Theory, 10, 99-127 (1977) · Zbl 0363.60104
[10] Willard, D. E., Log-logarithmic worst-case range queries are possible in space Θ \((N)\), Inform. Process. Lett., 17, 81-89 (1983) · Zbl 0509.68106
[11] Willard, D., New trie data structures which support very fast search operations, J. Comput. System Sci., 28, 395-419 (1984) · Zbl 0541.68037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.