skip to main content
article

Equivalence between priority queues and sorting

Published:01 December 2007Publication History
Skip Abstract Section

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.

References

  1. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  2. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  3. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  4. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  5. Comrie, L. J. 1929--30. The hollerith and powers tabulating machines. Trans. Office Mach. Users' Assoc., Ltd, 25--37.Google ScholarGoogle Scholar
  6. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms, Second ed. The MIT Press, Cambridge, MA. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Dijkstra, E. W. 1959. A note on two problems in connection with graphs. Numer. Math. 1, 269--271.Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. Dumey, A. I. 1956. Indexing for rapid random access memory systems. Comput. Automat. 5, 12, 6--9.Google ScholarGoogle Scholar
  9. Ford, L. R., and Johnson, S. M. 1959. A tournament problem. Amer. Math. Month. 66, 5, 387--389.Google ScholarGoogle ScholarCross RefCross Ref
  10. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  11. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  12. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  13. Han, Y. 2001. Improved fast integer sorting in linear space. Inf. Comput. 170, 8, 81--94. (Announced at STACS'00 and SODA'01.) Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  15. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  16. Kernighan, B., and Ritchie, D. 1988. The C Programming Language, Second ed. Prentice-Hall, Englewood Cliffs, NJ. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  18. Prim, R. C. 1957. Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1389--1401.Google ScholarGoogle ScholarCross RefCross Ref
  19. Tarjan, R. E. 1975. Efficiency of a good but not linear set union algorithm. J. ACM 22, 2, 215--225. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  21. Thorup, M. 2000. On RAM priority queues. SIAM J. Comput. 30, 1, 86--109. (Announced at SODA'96.) Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  23. Thorup, M. 2003a. Combinatorial power in multimedia processors. ACM SIGARCH Comput. Architect. News 31, 5, 5--11. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  25. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  26. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  27. Willard, D. E., and Lueker, G. S. 1985. Adding range restriction capability to dynamic data structures. J. ACM 32, 3, 597--617. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Equivalence between priority queues and sorting

              Recommendations

              Comments

              Login options

              Check if you have access through your login credentials or your institution to get full access on this article.

              Sign in

              Full Access

              • Published in

                cover image Journal of the ACM
                Journal of the ACM  Volume 54, Issue 6
                December 2007
                185 pages
                ISSN:0004-5411
                EISSN:1557-735X
                DOI:10.1145/1314690
                Issue’s Table of Contents

                Copyright © 2007 ACM

                Publisher

                Association for Computing Machinery

                New York, NY, United States

                Publication History

                • Published: 1 December 2007
                Published in jacm Volume 54, Issue 6

                Permissions

                Request permissions about this article.

                Request Permissions

                Check for updates

                Qualifiers

                • article

              PDF Format

              View or Download as a PDF file.

              PDF

              eReader

              View online with eReader.

              eReader