Abstract
We present a general deterministic linear space reduction from priority queues to sorting implying that if we can sort up to n keys in S(n) time per key, then there is a priority queue supporting delete and insert in O(S(n)) time and find-min in constant time. Conversely, a priority queue can trivially be used for sorting: first insert all keys to be sorted, then extract them in sorted order by repeatedly deleting the minimum. Asymptotically, this settles the complexity of priority queues in terms of that of sorting.
Previously, at SODA'96, such a result was presented by the author for the special case of monotone priority queues where the minimum is not allowed to decrease.
Besides nailing down the complexity of priority queues to that of sorting, and vice versa, our result yields several improved bounds for linear space integer priority queues with find-min in constant time:
Deterministically. We get O(log log n) update time using a sorting algorithm of Han from STOC'02. This improves the O((log log n)(log log log n)) update time of Han from SODA'01.
Randomized. We get O(√log log n) expected update time using a randomized sorting algorithm of Han and Thorup from FOCS'02. This improves the O(log log n) expected update time of Thorup from SODA'96.
Deterministically in AC0 (without multiplication). For any ε > 0, we get O((log log n)1+ε) update time using an AC0 sorting algorithm of Han and Thorup from FOCS'02. This improves the O((log log n)2) update time of Thorup from SODA'98.
Randomized in AC0. We get O(log log n) expected update time using a randomized AC0 sorting algorithm of Thorup from SODA'97. This improves the O((log log n)1+ε) expected update time of Thorup also from SODA'97.
The above bounds assume that each integer is stored in a single word and that word operations take unit time as in the word RAM.
- Alstrup, S., Husfeldt, T., Rauhe, T., and Thorup, M. 2005. Black box for constant-time insertion in priority queues (note). ACM Trans. Algor. 1, 1, 102--106. Google ScholarDigital Library
- Andersson, A., Miltersen, P., and Thorup, M. 1999. Fusion trees can be implemented with AC0 instructions only. Theor. Comput. Sc. 215, 1-2, 337--344. Google ScholarDigital Library
- Andersson, A., and Thorup, M. 2007. Dynamic ordered sets with exponential search trees. J. ACM 54, 3, Article 13. (Combines results announed at FOCS'96, STOC'00, and SODA'01.) Google ScholarDigital Library
- Beame, P., and Fich, F. 2002. Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci. 65, 1, 38--72. (Announced at STOC'99.) Google ScholarDigital Library
- Comrie, L. J. 1929--30. The hollerith and powers tabulating machines. Trans. Office Mach. Users' Assoc., Ltd, 25--37.Google Scholar
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms, Second ed. The MIT Press, Cambridge, MA. Google ScholarDigital Library
- Dijkstra, E. W. 1959. A note on two problems in connection with graphs. Numer. Math. 1, 269--271.Google ScholarDigital Library
- Dumey, A. I. 1956. Indexing for rapid random access memory systems. Comput. Automat. 5, 12, 6--9.Google Scholar
- Ford, L. R., and Johnson, S. M. 1959. A tournament problem. Amer. Math. Month. 66, 5, 387--389.Google ScholarCross Ref
- Fredman, M. L., and Saks, M. E. 1989. The cell probe complexity of dynamic data structures. In Proceedings of the 21st Symposium on Theory of Computing (STOC). ACM, New York, 345--354. Google ScholarDigital Library
- Fredman, M. L., and Willard, D. E. 1993. Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47, 424--436. (Announced at STOC'90.) Google ScholarDigital Library
- Fredman, M. L., and Willard, D. E. 1994. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48, 533--551. Google ScholarDigital Library
- Han, Y. 2001. Improved fast integer sorting in linear space. Inf. Comput. 170, 8, 81--94. (Announced at STACS'00 and SODA'01.) Google ScholarDigital Library
- Han, Y. 2004. Deterministic sorting in O(n log log n) time and linear space. J. Algorithms 50, 1, 95--105. (Announced at STOC'02.) Google ScholarDigital Library
- Han, Y., and Thorup, M. 2002. Integer sorting in O(n&sqrt;log log n) expected time and linear space. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los, Alamitos, CA, 135--144. Google ScholarDigital Library
- Kernighan, B., and Ritchie, D. 1988. The C Programming Language, Second ed. Prentice-Hall, Englewood Cliffs, NJ. Google ScholarDigital Library
- Mendelson, R., Tarjan, R., Thorup, M., and Zwick, U. 2006. Melding priority queues. ACM Trans. Algor. 2, 4, 535--557. (Announced at SODA'03 and SWAT'04.) Google ScholarDigital Library
- Prim, R. C. 1957. Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1389--1401.Google ScholarCross Ref
- Tarjan, R. E. 1975. Efficiency of a good but not linear set union algorithm. J. ACM 22, 2, 215--225. Google ScholarDigital Library
- Thorup, M. 1998. Faster deterministic sorting and priority queues in linear space. In Proceedings of the 9th Symposium on Discrete Algorithms (SODA). ACM, New York, 550--555. Google ScholarDigital Library
- Thorup, M. 2000. On RAM priority queues. SIAM J. Comput. 30, 1, 86--109. (Announced at SODA'96.) Google ScholarDigital Library
- Thorup, M. 2002. Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations. J. Algor. 42, 2, 205--230. (Announced at SODA'97.) Google ScholarDigital Library
- Thorup, M. 2003a. Combinatorial power in multimedia processors. ACM SIGARCH Comput. Architect. News 31, 5, 5--11. Google ScholarDigital Library
- Thorup, M. 2003b. On AC0 implementations of fusion trees and atomic heaps. In Proceedings of the 14th Symposium on Discrete Algorithms (SODA). ACM, New York, 699--707. Google ScholarDigital Library
- Thorup, M. 2004. Integer priority queues with decrease key in constant time and the single source shortest paths problem. J. Comput. Syst. Sci. 69, 3, 330--353. (Announced at STOC'03.) Google ScholarDigital Library
- Willard, D. E. 2000. Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree. SIAM J. Comput. 29, 3, 1030--1049. (Announced at SODA'92.) Google ScholarDigital Library
- Willard, D. E., and Lueker, G. S. 1985. Adding range restriction capability to dynamic data structures. J. ACM 32, 3, 597--617. Google ScholarDigital Library
Index Terms
Equivalence between priority queues and sorting
Recommendations
Integer priority queues with decrease key in constant time and the single source shortest paths problem
STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computingWe consider Fibonacci heap style integer priority queues supporting insert and decrease key operations in constant time. We present a deterministic linear space solution that with n integer keys support delete in O(log log n) time. If the integers are ...
Deterministic sorting in O(nlog log n) time and linear space
STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computingWe present a fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in the range {0, 1, 2, …, m—1} in linear space in O(n log log n) time. This improves our previous result [8] which sorts in O(n log log n log ...
On RAM Priority Queues
Priority queues are some of the most fundamental data structures. For example, they are used directly for task scheduling in operating systems. Moreover, they are essential to greedy algorithms. We study the complexity of integer priority queue ...
Comments