{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T21:17:42Z","timestamp":1768684662819,"version":"3.49.0"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,4,21]],"date-time":"2017-04-21T00:00:00Z","timestamp":1492732800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1007\/s00224-017-9760-2","type":"journal-article","created":{"date-parts":[[2017,4,21]],"date-time":"2017-04-21T05:48:50Z","timestamp":1492753730000},"page":"606-636","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Optimizing Binary Heaps"],"prefix":"10.1007","volume":"61","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7714-5588","authenticated-orcid":false,"given":"Stefan","family":"Edelkamp","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amr","family":"Elmasry","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jyrki","family":"Katajainen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,4,21]]},"reference":[{"issue":"1","key":"9760_CR1","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1145\/1077464.1077471","volume":"1","author":"S Alstrup","year":"2005","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T., Thorup, M.: Black box for constant-time insertion in priority queues. ACM Trans. Algorithms 1(1), 102\u2013106 (2005)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"9760_CR2","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jagm.1996.0011","volume":"20","author":"B Bollob\u00e1s","year":"1996","unstructured":"Bollob\u00e1s, B., Fenner, T., Frieze, A.: On the best case of heapsort. J. Algorithms 20(2), 205\u2013217 (1996)","journal-title":"J. Algorithms"},{"key":"9760_CR3","doi-asserted-by":"crossref","unstructured":"Brodal, G. S., Nielsen, J. S., Truelsen, J.: Strictly implicit priority queues: on the number of moves and worst-case time WADS 2015, vol. 9214, pp 91\u2013102. Springer, Heidelberg (2015)","DOI":"10.1007\/978-3-319-21840-3_8"},{"issue":"3","key":"9760_CR4","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0207026","volume":"7","author":"MR Brown","year":"1978","unstructured":"Brown, M. R.: Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7(3), 298\u2013319 (1978)","journal-title":"SIAM J. Comput."},{"key":"9760_CR5","doi-asserted-by":"crossref","unstructured":"Bruun, A., Edelkamp, S., Katajainen, J., Rasmussen, J.: Policy-based benchmarking of weak heaps and their relatives SEA 2010, LNCS, vol. 6049, pp 424\u2013435. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-13193-6_36"},{"issue":"4","key":"9760_CR6","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0020-0190(87)90142-6","volume":"24","author":"S Carlsson","year":"1987","unstructured":"Carlsson, S.: A variant of Heapsort with almost optimal number of comparisons. Inform. Process. Lett. 24(4), 247\u2013250 (1987)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"9760_CR7","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0020-0190(91)90144-7","volume":"37","author":"S Carlsson","year":"1991","unstructured":"Carlsson, S.: An optimal algorithm for deleting the root of a heap. Inform. Process. Lett. 37(2), 117\u2013120 (1991)","journal-title":"Inform. Process. Lett."},{"issue":"1-2","key":"9760_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(95)00152-2","volume":"164","author":"S Carlsson","year":"1996","unstructured":"Carlsson, S., Chen, J., Mattsson, C.: Heaps with bits. Theoret. Comput. Sci. 164(1-2), 1\u201312 (1996)","journal-title":"Theoret. Comput. Sci."},{"key":"9760_CR9","doi-asserted-by":"crossref","unstructured":"Carlsson, S., Munro, J. I., Poblete, P. V.: An implicit binomial queue with constant insertion time SWAT 1988, LNCS, vol. 318, pp 1\u201313. Springer, Heidelberg (1988)","DOI":"10.1007\/3-540-19487-8_1"},{"key":"9760_CR10","doi-asserted-by":"crossref","unstructured":"Chen, J., Edelkamp, S., Elmasry, A., Katajainen, J.: In-Place heap construction with optimized comparisons, moves, and cache misses MFCS 2012, LNCS, vol. 7464, pp 259\u2013270. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-32589-2_25"},{"key":"9760_CR11","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C.: Introduction to Algorithms, 3th edn. The MIT Press, Cambridge (2009)","edition":"3th edn"},{"key":"9760_CR12","unstructured":"Darwish, O., Elmasry, A., Katajainen, J.: Memory-adjustable navigation piles with applications to sorting and convex hulls. E-print arXiv: 1510.07185 , arXiv.org Ithaca (2015)"},{"issue":"11","key":"9760_CR13","doi-asserted-by":"crossref","first-page":"1343","DOI":"10.1145\/50087.50096","volume":"31","author":"JR Driscoll","year":"1988","unstructured":"Driscoll, J. R., Gabow, H. N., Shrairman, R., Tarjan, R. E.: Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Commun. ACM 31(11), 1343\u20131354 (1988)","journal-title":"Commun. ACM"},{"issue":"3","key":"9760_CR14","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1007\/BF01990520","volume":"33","author":"RD Dutton","year":"1993","unstructured":"Dutton, R. D.: Weak-heap sort. BIT 33(3), 372\u2013381 (1993)","journal-title":"BIT"},{"key":"9760_CR15","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/j.jda.2012.04.010","volume":"16","author":"S Edelkamp","year":"2012","unstructured":"Edelkamp, S., Elmasry, A., Katajainen, J.: The weak-heap data structure: Variants and applications. J. Discrete Algorithms 16, 187\u2013205 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"9760_CR16","unstructured":"Edelkamp, S., Elmasry, A., Katajainen, J.: A catalogue of weak-heap programs. CPH STL Report 2012-2. Dept. Comput. Sci., Univ, Copenhagen, Copenhagen (2012)"},{"key":"9760_CR17","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.jda.2013.07.002","volume":"23","author":"S Edelkamp","year":"2013","unstructured":"Edelkamp, S., Elmasry, A., Katajainen, J.: Weak heaps engineered. J. Discrete Algorithms 23, 83\u201397 (2013)","journal-title":"J. Discrete Algorithms"},{"key":"9760_CR18","unstructured":"Edelkamp, S., Elmasry, A., Katajainen, J.: Strengthened lazy heaps: Surpassing the lower bounds for binary heaps. E-print arXiv: 1407.3377 , arXiv.org Ithaca (2014)"},{"key":"9760_CR19","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Elmasry, A., Katajainen, J.: An in-place Priority Queue with O(1) Time for Push and lg n + O(1) Comparisons for Pop CSR 2015, LNCS, vol. 9139, pp 1\u201315. Springer, Heidelberg (2015)","DOI":"10.1007\/978-3-319-20297-6_14"},{"issue":"1","key":"9760_CR20","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/1435375.1435389","volume":"5","author":"A Elmasry","year":"2008","unstructured":"Elmasry, A., Jensen, C., Katajainen, J.: Multipartite priority queues. ACM Trans. Algorithms 5(1), 14:1\u201314:19 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9760_CR21","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/s00224-011-9357-0","volume":"50","author":"A Elmasry","year":"2012","unstructured":"Elmasry, A., Jensen, C., Katajainen, J.: Two skew-binary numeral systems and one application. Theory Comput. Syst. 50(1), 185\u2013211 (2012)","journal-title":"Theory Comput. Syst."},{"key":"9760_CR22","volume-title":"Towards ultimate binary heaps CPH STL report 2013-1","author":"A Elmasry","year":"2013","unstructured":"Elmasry, A., Katajainen, J.: Towards ultimate binary heaps CPH STL report 2013-1. Dept. Comput. Sci., Univ, Copenhagen, Copenhagen (2013)"},{"key":"9760_CR23","unstructured":"van Emde Boas, P.: Thirty nine years of stratified trees ISCIM 2013, vol. 1, pp 1\u201314. Epoka University, Tirana (2013)"},{"issue":"2","key":"9760_CR24","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1007\/BF01182770","volume":"11","author":"R Fleischer","year":"1994","unstructured":"Fleischer, R.: A tight lower bound for the worst case of Bottom-up-heapsort. Algorithmica 11(2), 104\u2013115 (1994)","journal-title":"Algorithmica"},{"issue":"3","key":"9760_CR25","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1006\/inco.1993.1009","volume":"102","author":"R Fleischer","year":"1993","unstructured":"Fleischer, R., Sinha, B., Uhrig, C.: A lower bound for the worst case of Bottom-up-heapsort. Inform. and Comput. 102(3), 263\u2013279 (1993)","journal-title":"Inform. and Comput."},{"issue":"12","key":"9760_CR26","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/355588.365103","volume":"7","author":"RW Floyd","year":"1964","unstructured":"Floyd, R. W.: Algorithm 245: Treesort 3. Commun. ACM 7(12), 701 (1964)","journal-title":"Commun. ACM"},{"issue":"4","key":"9760_CR27","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1137\/0215068","volume":"15","author":"GH Gonnet","year":"1986","unstructured":"Gonnet, G. H., Munro, J. I.: Heaps on heaps. SIAM J. Comput. 15(4), 964\u2013971 (1986)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9760_CR28","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.jalgor.2003.09.001","volume":"50","author":"Y Han","year":"2004","unstructured":"Han, Y.: Deterministic sorting in O(n log log n) time and linear space. J. Algorithms 50(1), 96\u2013105 (2004)","journal-title":"J. Algorithms"},{"key":"9760_CR29","first-page":"135","volume-title":"FOCS 2002","author":"Y Han","year":"2002","unstructured":"Han, Y., Thorup, M.: Integer sorting in O ( n log log n ) ${O}(n \\sqrt {\\log \\log n})$ expected time and linear space FOCS 2002, pp 135\u2013144. IEEE Computer Society, Los Alamitos (2002)"},{"key":"9760_CR30","volume-title":"FUN 2004","author":"NJA Harvey","year":"2004","unstructured":"Harvey, N. J. A., Zatloukal, K. C.: The Post-Order Heap FUN 2004 (2004)"},{"issue":"1","key":"9760_CR31","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/0196-6774(91)90027-V","volume":"12","author":"R Hayward","year":"1991","unstructured":"Hayward, R., McDiarmid, C.: Average case analysis of heap building by repeated insertion. J. Algorithms 12(1), 126\u2013153 (1991)","journal-title":"J. Algorithms"},{"issue":"3","key":"9760_CR32","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0020-0190(75)90001-0","volume":"4","author":"DB Johnson","year":"1975","unstructured":"Johnson, D. B.: Priority queues with update and finding minimum spanning trees. Inform. Process. Lett. 4(3), 53\u201357 (1975)","journal-title":"Inform. Process. Lett."},{"key":"9760_CR33","unstructured":"Katajainen, J.: The Ultimate Heapsort CATS 1998, Australian computer science communications, vol. 20, pp 87\u201395. Springer, Singapore (1998)"},{"key":"9760_CR34","unstructured":"Knuth, D. E. The Art of Computer Programming: Fundamental Algorithms, 3rd edn, vol. 1. Addison Wesley Longman, Reading (1997)"},{"key":"9760_CR35","unstructured":"Knuth, D. E. The Art of Computer Programming: Sorting and Searching, 2nd edn, vol. 3. Addison Wesley Longman, Reading (1998)"},{"issue":"3","key":"9760_CR36","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1006\/jagm.1993.1021","volume":"14","author":"C Levcopoulos","year":"1993","unstructured":"Levcopoulos, C., Petersson, O.: Adaptive heapsort. J. Algorithms 14(3), 395\u2013413 (1993)","journal-title":"J. Algorithms"},{"issue":"3","key":"9760_CR37","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1016\/0196-6774(89)90033-3","volume":"10","author":"CJH McDiarmid","year":"1989","unstructured":"McDiarmid, C. J. H., Reed, B. A.: Building heaps fast. J. Algorithms 10 (3), 352\u2013365 (1989)","journal-title":"J. Algorithms"},{"issue":"1","key":"9760_CR38","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0202005","volume":"2","author":"J Nievergelt","year":"1973","unstructured":"Nievergelt, J., Reingold, E.: Binary search trees of bounded balance. SIAM J. Comput. 2(1), 33\u201343 (1973)","journal-title":"SIAM J. Comput."},{"key":"9760_CR39","unstructured":"Overmars, M. H.: The Design of Dynamic Data Structures, LNCS, vol. 156. Springer, Heidelberg (1983)"},{"key":"9760_CR40","doi-asserted-by":"crossref","unstructured":"Sack, J. R., Strothotte, T.: A characterization of heaps and its applications 86(1), 69\u201386 (1990)","DOI":"10.1016\/0890-5401(90)90026-E"},{"issue":"1","key":"9760_CR41","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1006\/jagm.1993.1031","volume":"15","author":"R Schaffer","year":"1993","unstructured":"Schaffer, R., Sedgewick, R.: The analysis of heapsort. J. Algorithms 15(1), 76\u2013100 (1993)","journal-title":"J. Algorithms"},{"issue":"1","key":"9760_CR42","doi-asserted-by":"crossref","first-page":"75","DOI":"10.3233\/FI-2012-751","volume":"120","author":"MA Suchenek","year":"2012","unstructured":"Suchenek, M. A.: Elementary yet precise worst-case analysis of Floyd\u2019s heap-construction program. Fund. Inform. 120(1), 75\u201392 (2012)","journal-title":"Fund. Inform."},{"issue":"6","key":"9760_CR43","doi-asserted-by":"crossref","first-page":"28:1","DOI":"10.1145\/1314690.1314692","volume":"54","author":"M Thorup","year":"2007","unstructured":"Thorup, M.: Equivalence between priority queues and sorting. J. ACM 54(6), 28:1\u201328:27 (2007)","journal-title":"J. ACM"},{"issue":"4","key":"9760_CR44","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"},{"key":"9760_CR45","doi-asserted-by":"crossref","first-page":"2274","DOI":"10.1016\/j.proeng.2012.01.300","volume":"29","author":"X Wang","year":"2012","unstructured":"Wang, X., Wu, Y., Zhu, D.: A new variant of in-place sort algorithm. Procedia Eng. 29, 2274\u20132278 (2012)","journal-title":"Procedia Eng."},{"issue":"1","key":"9760_CR46","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0890-5401(92)90005-Z","volume":"97","author":"I Wegener","year":"1992","unstructured":"Wegener, I.: The worst case complexity of McDiarmid and Reed\u2019s variant of Bottom-up Heapsort is less than n log n + 1.1n. Inform. and Comput. 97(1), 86\u201396 (1992)","journal-title":"Inform. and Comput."},{"issue":"1","key":"9760_CR47","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). Theoret. Comput. Sci. 118(1), 81\u201398 (1993)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"9760_CR48","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1093\/comjnl\/36.3.286","volume":"36","author":"I Wegener","year":"1993","unstructured":"Wegener, I.: A simple modification of Xunrang and Yuzhang\u2019s Heapsort variant improving its complexity significantly. Comput. J. 36(3), 286\u2013288 (1993)","journal-title":"Comput. J."},{"issue":"6","key":"9760_CR49","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"JWJ Williams","year":"1964","unstructured":"Williams, J. W. J.: Algorithm 232: Heapsort. Commun. ACM 7(6), 347\u2013348 (1964)","journal-title":"Commun. ACM"},{"issue":"3","key":"9760_CR50","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1093\/comjnl\/33.3.281","volume":"33","author":"G Xunrang","year":"1990","unstructured":"Xunrang, G., Yuzhang, Z.: A new Heapsort algorithm and the analysis of its complexity. Comput. J. 33(3), 281\u2013282 (1990)","journal-title":"Comput. J."},{"issue":"2","key":"9760_CR51","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1016\/0304-3975(94)00113-8","volume":"134","author":"G Xunrang","year":"1994","unstructured":"Xunrang, G., Yuzhang, Z.: Asymptotic optimal Heapsort algorithm. Theoret. Comput. Sci. 134(2), 559\u2013565 (1994)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"9760_CR52","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(95)00233-2","volume":"163","author":"G Xunrang","year":"1996","unstructured":"Xunrang, G., Yuzhang, Z.: Optimal heapsort algorithm. Theoret. Comput. Sci. 163(1\u20132), 239\u2013243 (1996)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9760-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9760-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9760-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,6]],"date-time":"2020-10-06T01:08:34Z","timestamp":1601946514000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9760-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,21]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["9760"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9760-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,21]]}}}