Abstract
A priority queue is a fundamental data structure that maintains a dynamic ordered set of keys and supports the followig basic operations: insertion of a key, deletion of a key, and finding the smallest key. The complexity of the priority queue is closely related to that of sorting: A priority queue can be used to implement a sorting algorithm trivially. Thorup [11] proved that the converse is also true in the RAM model. In particular, he designed a priority queue that uses the sorting algorithm as a black box, such that the per-operation cost of the priority queue is asymptotically the same as the per-key cost of sorting. In this paper, we prove an analogous result in the external memory model, showing that priority queues are computationally equivalent to sorting in external memory, under some mild assumptions. The reduction provides a possibility for proving lower bounds for external sorting via showing a lower bound for priority queues.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aggarwal, A., Vitter, J.S.: The input/output complexity of sorting and related problems. Communications of the ACM 31(9), 1116–1127 (1988)
Arge, L.: The buffer tree: A technique for designing batched external data structures. Algorithmica 37(1), 1–24 (2003)
Arge, L., Bender, M., Demaine, E., Holland-Minkley, B., Munro, J.: Cache-oblivious priority queue and graph algorithm applications. In: Proc. ACM Symposium on Theory of Computing, pp. 268–276. ACM (2002)
Brodal, G., Katajainen, J.: Worst-case efficient external-memory priority queues. In: Proc. Scandinavian Workshop on Algorithms Theory, pp. 107–118 (1998)
Fadel, R., Jakobsen, K., Katajainen, J., Teuhola, J.: Heaps and heapsort on secondary storage. Theoretical Computer Science 220(2), 345–362 (1999)
Fredman, F.W., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. In: Proc. 31st Annu. IEEE Sympos. Found. Comput. Sci., pp. 719–725 (1990)
Han, Y.: Deterministic sorting in o (n loglogn) time and linear space. Journal of Algorithms 50(1), 96–105 (2004)
Han, Y., Thorup, M.: Integer sorting in \(o (n\sqrt{\log\log n})\) expected time and linear space. In: Proc. IEEE Symposium on Foundations of Computer Science, pp. 135–144. IEEE (2002)
Larsen, K.G.: The cell probe complexity of dynamic range counting. In: Proc. ACM Symposium on Theory of Computing (2012)
Pǎtraşcu, M.: Unifying the landscape of cell-probe lower bounds. SIAM Journal on Computing 40(3) (2011)
Thorup, M.: Equivalence between priority queues and sorting. Journal of the ACM 54(6), 28 (2007)
Vitter, J.: External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys 33(2), 209–271 (2001)
Wei, Z., Yi, K.: Equivalence between Priority Queues and Sorting in External Memory. arXiv: 1207.4383 (2014)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wei, Z., Yi, K. (2014). Equivalence between Priority Queues and Sorting in External Memory. In: Schulz, A.S., Wagner, D. (eds) Algorithms - ESA 2014. ESA 2014. Lecture Notes in Computer Science, vol 8737. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44777-2_68
Download citation
DOI: https://doi.org/10.1007/978-3-662-44777-2_68
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44776-5
Online ISBN: 978-3-662-44777-2
eBook Packages: Computer ScienceComputer Science (R0)