{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T16:19:42Z","timestamp":1781194782711,"version":"3.54.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,3,23]],"date-time":"2010-03-23T00:00:00Z","timestamp":1269302400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,8]]},"DOI":"10.1007\/s00453-010-9400-6","type":"journal-article","created":{"date-parts":[[2010,3,22]],"date-time":"2010-03-22T15:20:08Z","timestamp":1269271208000},"page":"585-620","source":"Crossref","is-referenced-by-count":10,"title":["On Sorting, Heaps, and Minimum Spanning Trees"],"prefix":"10.1007","volume":"57","author":[{"given":"Gonzalo","family":"Navarro","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rodrigo","family":"Paredes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,3,23]]},"reference":[{"issue":"2","key":"9400_CR1","first-page":"213","volume":"37","author":"R. Ahuja","year":"1990","unstructured":"Ahuja, R., Mehlhorn, K., Orlin, J., Tarjan, R.: Faster algorithms for the shortest path problem. J.\u00a0ACM 37(2), 213\u2013223 (1990)","journal-title":"J.\u00a0ACM"},{"key":"9400_CR2","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/3-540-60220-8_74","volume-title":"Proc. 4th Intl. Workshop on Algorithms and Data Structures (WADS\u201995)","author":"L. Arge","year":"1995","unstructured":"Arge, L.: The buffer tree: a new technique for optimal I\/O-algorithms (extended abstract). In: Proc. 4th Intl. Workshop on Algorithms and Data Structures (WADS\u201995). LNCS, vol.\u00a0995, pp.\u00a0334\u2013345. Springer, Berlin (1995)"},{"key":"9400_CR3","volume-title":"Modern Information Retrieval","author":"R.A. Baeza-Yates","year":"1999","unstructured":"Baeza-Yates, R.A., Ribeiro-Neto, B.: Modern Information Retrieval. Addison-Wesley, Reading (1999)"},{"key":"9400_CR4","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.: Organization and maintenance of large ordered indices. Acta Inf. 1, 173\u2013189 (1972)","journal-title":"Acta Inf."},{"issue":"4","key":"9400_CR5","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J.\u00a0Comput. Syst. Sci. 7(4), 448\u2013461 (1973)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9400_CR6","doi-asserted-by":"crossref","unstructured":"Brengel, K., Crauser, A., Ferragina, P., Meyer, U.: An experimental study of priority queues in external memory. ACM J. Exp. Algorithmics 5(17) (2000)","DOI":"10.1145\/351827.384259"},{"key":"9400_CR7","doi-asserted-by":"crossref","unstructured":"Brodal, G., Fagerberg, R.: On the limits of cache-obliviousness. In: Proc. 35th ACM Symp. on Theory of Computing (STOC\u201903), pp.\u00a0307\u2013315 (2003)","DOI":"10.1145\/780542.780589"},{"key":"9400_CR8","series-title":"LNCS","first-page":"107","volume-title":"Proc. 6th Scandinavian Workshop on Algorithm Theory (SWAT\u201998)","author":"G. Brodal","year":"1998","unstructured":"Brodal, G., Katajainen, J.: Worst-case external-memory priority queues. In: Proc. 6th Scandinavian Workshop on Algorithm Theory (SWAT\u201998). LNCS, vol.\u00a01432, pp.\u00a0107\u2013118. Springer, Berlin (1998)"},{"issue":"6","key":"9400_CR9","first-page":"1028","volume":"47","author":"B. Chazelle","year":"2000","unstructured":"Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann type complexity. J.\u00a0ACM 47(6), 1028\u20131047 (2000)","journal-title":"J.\u00a0ACM"},{"key":"9400_CR10","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1137\/0205051","volume":"5","author":"D. Cheriton","year":"1976","unstructured":"Cheriton, D., Tarjan, R.E.: Finding minimum spanning trees. SIAM J. Comput. 5, 724\u2013742 (1976)","journal-title":"SIAM J. Comput."},{"key":"9400_CR11","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd\u00a0edn. MIT Press, New York (2001)","edition":"2"},{"key":"9400_CR12","unstructured":"Dementiev, R.: Algorithm Engineering for Large Data Sets. PhD\u00a0thesis, Saarland University, Germany (2006)"},{"issue":"6","key":"9400_CR13","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1002\/spe.844","volume":"38","author":"R. Dementiev","year":"2007","unstructured":"Dementiev, R., Kettner, L., Sanders, P.: STXXL: standard template library for XXL data sets. Softw. Pract. Exp. 38(6), 589\u2013637 (2007)","journal-title":"Softw. Pract. Exp."},{"issue":"2","key":"9400_CR14","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/S0304-3975(99)00006-7","volume":"220","author":"R. Fadel","year":"1999","unstructured":"Fadel, R., Jakobsen, K., Katajainen, J., Teuhola, J.: Heaps and heapsort on secondary storage. Theor. Comput. Sci. 220(2), 345\u2013362 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"9400_CR15","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/355588.365103","volume":"7","author":"R.W. Floyd","year":"1964","unstructured":"Floyd, R.W.: Algorithm 245 (treesort). Commun. ACM 7, 701 (1964)","journal-title":"Commun. ACM"},{"issue":"1","key":"9400_CR16","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01840439","volume":"1","author":"M.L. Fredman","year":"1986","unstructured":"Fredman, M.L., Sedgewick, R., Sleator, D.D., Tarjan, R.E.: The pairing heap: a new form of self-adjusting heap. Algorithmica 1(1), 111\u2013129 (1986)","journal-title":"Algorithmica"},{"issue":"3","key":"9400_CR17","first-page":"596","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J.\u00a0ACM 34(3), 596\u2013615 (1987)","journal-title":"J.\u00a0ACM"},{"key":"9400_CR18","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proc. 40th IEEE Symp. on Foundations on Computer Science (FOCS\u201999), pp.\u00a0285\u2013297 (1999)","DOI":"10.1109\/SFFCS.1999.814600"},{"issue":"7","key":"9400_CR19","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"C.A.R. Hoare","year":"1961","unstructured":"Hoare, C.A.R.: Algorithm 65 (find). Commun. ACM 4(7), 321\u2013322 (1961)","journal-title":"Commun. ACM"},{"key":"9400_CR20","unstructured":"Hutchinson, D., Maheshwari, A., Sack, J., Velicescu, R.: Early experiences in implementing buffer trees. In: Proc. 1st Intl. Workshop on Algorithm Engineering (WAE\u201997), pp.\u00a092\u2013103 (1997)"},{"issue":"3","key":"9400_CR21","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1002\/rsa.3240040303","volume":"4","author":"S. Janson","year":"1993","unstructured":"Janson, S., Knuth, D., \u0141uczak, T., Pittel, B.: The birth of the giant component. Random Struct. Algorithms 4(3), 233\u2013358 (1993)","journal-title":"Random Struct. Algorithms"},{"key":"9400_CR22","unstructured":"Katriel, I., Sanders, P., Tr\u00e4ff, J.: A practical minimum spanning tree algorithm using the cycle property. Research Report MPI-I-2002-1-003, Max-Planck-Institut f\u00fcr Informatik, October (2002)"},{"key":"9400_CR23","series-title":"LNCS","first-page":"679","volume-title":"Proc. 11th European Symp. on Algorithms (ESA\u201903)","author":"I. Katriel","year":"2003","unstructured":"Katriel, I., Sanders, P., Tr\u00e4ff, J.: A practical minimum spanning tree algorithm using the cycle property. In: Proc. 11th European Symp. on Algorithms (ESA\u201903). LNCS, vol.\u00a02832, pp.\u00a0679\u2013690. Springer, Berlin (2003)"},{"key":"9400_CR24","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J.B. Kruskal","year":"1956","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7, 48\u201350 (1956)","journal-title":"Proc. Am. Math. Soc."},{"key":"9400_CR25","first-page":"169","volume-title":"Proc. 8th IEEE Symp. on Parallel and Distributed Processing (SPDP\u201996)","author":"V. Kumar","year":"1996","unstructured":"Kumar, V., Schwabe, E.: Improved algorithms and data structures for solving graph problems in external memory. In: Proc. 8th IEEE Symp. on Parallel and Distributed Processing (SPDP\u201996), p.\u00a0169. IEEE Computer Society Press, New York (1996)"},{"key":"9400_CR26","first-page":"224","volume-title":"Proc. 6th ACM-SIAM Workshop on Algorithm Engineering and Experiments and 1st ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics (ALENEX-ANALCO\u201904)","author":"C. Mart\u00ednez","year":"2004","unstructured":"Mart\u00ednez, C.: Partial quicksort. In: Proc. 6th ACM-SIAM Workshop on Algorithm Engineering and Experiments and 1st ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics (ALENEX-ANALCO\u201904), pp.\u00a0224\u2013228. SIAM, New York (2004)"},{"key":"9400_CR27","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1007\/BFb0028279","volume-title":"Proc. 2nd Workshop Algorithms and Data Structures (WADS\u201991)","author":"B. Moret","year":"1991","unstructured":"Moret, B., Shapiro, H.: An empirical analysis of algorithms for constructing a minimum spanning tree. In: Proc. 2nd Workshop Algorithms and Data Structures (WADS\u201991). LNCS, vol.\u00a0519, pp.\u00a0400\u2013411. Springer, Berlin (1991)"},{"key":"9400_CR28","unstructured":"Paredes, R.: Graphs for metric space searching. PhD thesis, University of Chile, Chile, 2008. Dept. of Computer Science Tech Report TR\/DCC-2008-10. Available at http:\/\/www.dcc.uchile.cl\/~raparede\/publ\/08PhDthesis.pdf"},{"key":"9400_CR29","first-page":"171","volume-title":"Proc. 8th Workshop on Algorithm Engineering and Experiments and 3rd Workshop on Analytic Algorithmics and Combinatorics (ALENEX-ANALCO\u201906)","author":"R. Paredes","year":"2006","unstructured":"Paredes, R., Navarro, G.: Optimal incremental sorting. In: Proc. 8th Workshop on Algorithm Engineering and Experiments and 3rd Workshop on Analytic Algorithmics and Combinatorics (ALENEX-ANALCO\u201906), pp.\u00a0171\u2013182. SIAM, New York (2006)"},{"issue":"1","key":"9400_CR30","first-page":"16","volume":"49","author":"S. Pettie","year":"2002","unstructured":"Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J.\u00a0ACM 49(1), 16\u201334 (2002)","journal-title":"J.\u00a0ACM"},{"key":"9400_CR31","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R.C. Prim","year":"1957","unstructured":"Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech.\u00a0J. 36, 1389\u20131401 (1957)","journal-title":"Bell Syst. Tech.\u00a0J."},{"key":"9400_CR32","doi-asserted-by":"crossref","unstructured":"Sanders, P.: Fast priority queues for cached memory. ACM J. Exp. Algorithmics 5 (2000)","DOI":"10.1145\/351827.384249"},{"issue":"2","key":"9400_CR33","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"issue":"1","key":"9400_CR34","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1137\/0215004","volume":"15","author":"D.D. Sleator","year":"1986","unstructured":"Sleator, D.D., Tarjan, R.E.: Self adjusting heaps. SIAM J. Comput. 15(1), 52\u201369 (1986)","journal-title":"SIAM J. Comput."},{"key":"9400_CR35","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Data Structures and Network Algorithms. SIAM, New York (1983)"},{"issue":"2","key":"9400_CR36","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Amortized computational complexity. SIAM J. Algebr. Discrete Methods 6(2), 306\u2013318 (1985)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"9400_CR37","unstructured":"R Development Core Team: R: A language and environment for statistical computing. R\u00a0Foundation for Statistical Computing, Vienna, Austria (2004)"},{"key":"9400_CR38","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Math. Syst. Theory 10, 99\u2013127 (1977)","journal-title":"Math. Syst. Theory"},{"issue":"2","key":"9400_CR39","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"J. Vitter","year":"2001","unstructured":"Vitter, J.: External memory algorithms and data structures: dealing with massive data. ACM Comput. Surv. 33(2), 209\u2013271 (2001). Version revised at 2007 from http:\/\/www.cs.duke.edu\/~jsv\/Papers\/Vit.IO_survey.pdf","journal-title":"ACM Comput. Surv."},{"issue":"4","key":"9400_CR40","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1145\/359460.359478","volume":"21","author":"J. Vuillemin","year":"1978","unstructured":"Vuillemin, J.: A data structure for manipulating priority queues. Commun. ACM 21(4), 309\u2013315 (1978)","journal-title":"Commun. ACM"},{"issue":"1","key":"9400_CR41","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0304-3975(93)90364-Y","volume":"118","author":"I. Wegener","year":"1993","unstructured":"Wegener, I.: bottom-up-heapsort, a new variant of heapsort beating, on an average, quicksort (if n is not very small). Theor. Comput. Sci. 118(1), 81\u201398 (1993)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"9400_CR42","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J. Williams","year":"1964","unstructured":"Williams, J.: Algorithm 232 (heapsort). Commun. ACM 7(6), 347\u2013348 (1964)","journal-title":"Commun. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9400-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9400-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9400-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,25]],"date-time":"2021-10-25T02:35:08Z","timestamp":1635129308000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9400-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,23]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["9400"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9400-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3,23]]}}}