{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T23:19:46Z","timestamp":1648595986374},"reference-count":26,"publisher":"Oxford University Press (OUP)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The Computer Journal"],"DOI":"10.1093\/comjnl\/bxw085","type":"journal-article","created":{"date-parts":[[2016,11,4]],"date-time":"2016-11-04T20:05:38Z","timestamp":1478289938000},"source":"Crossref","is-referenced-by-count":0,"title":["Heap Construction\u201450 Years Later"],"prefix":"10.1093","author":[{"given":"Stefan","family":"Edelkamp","sequence":"first","affiliation":[]},{"given":"Amr","family":"Elmasry","sequence":"additional","affiliation":[]},{"given":"Jyrki","family":"Katajainen","sequence":"additional","affiliation":[]}],"member":"286","published-online":{"date-parts":[[2016,12,5]]},"reference":[{"key":"2016120517351437000_bxw085v1.1","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","article-title":"Algorithm 232: Heapsort","volume":"7","author":"Williams","year":"1964","journal-title":"Commun. ACM"},{"key":"2016120517351437000_bxw085v1.2","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/355588.365103","article-title":"Algorithm 245: Treesort 3","volume":"7","author":"Floyd","year":"1964","journal-title":"Commun. ACM"},{"key":"2016120517351437000_bxw085v1.3","unstructured":"Cormen, T.H. , Leiserson, C.E. , Rivest, R.L. and Stein, C. (2009) Introduction to Algorithms (3nd edn). The MIT Press, Cambridge."},{"key":"2016120517351437000_bxw085v1.4","doi-asserted-by":"crossref","unstructured":"Chen, J. (1993) A framework for constructing heap-like structures in-place. In Proc. 4th Int. Symp. Algorithms and Computation, Lecture Notes in Computer Science, Vol. 762, pp. 118\u2013127. Springer, Berlin Heidelberg.","DOI":"10.1007\/3-540-57568-5_241"},{"key":"2016120517351437000_bxw085v1.5","unstructured":"Knuth, D.E. (1998) Sorting and Searching. In The Art of Computer Programming, 3 (2nd edn). Addison Wesley Longman, Reading."},{"key":"2016120517351437000_bxw085v1.6","unstructured":"Knuth, D.E. (1997) Fundamental Algorithms. In The Art of Computer Programming, 1 (3rd edn). Addison Wesley Longman, Reading."},{"key":"2016120517351437000_bxw085v1.7","doi-asserted-by":"crossref","unstructured":"Katajainen, J. and Tr\u00e4ff, J.L. (1997) A meticulous analysis of mergesort programs. In Proc. 3rd Italian Conf. Algorithms and Complexity, Lecture Notes in Computer Science, Vol. 1203, pp. 217\u2013228. Springer, Berlin Heidelberg.","DOI":"10.1007\/3-540-62592-5_74"},{"key":"2016120517351437000_bxw085v1.8","doi-asserted-by":"crossref","first-page":"15.1","DOI":"10.1145\/351827.384257","article-title":"Performance engineering case study: Heap construction","volume":"5","author":"Bojesen","year":"2000","journal-title":"ACM J. Exp. Algorithmics"},{"key":"2016120517351437000_bxw085v1.9","doi-asserted-by":"crossref","unstructured":"Elmasry, A. and Katajainen, J. (2012) Lean programs, branch mispredictions, and sorting. Proc. 6th Int. Conf. Fun with Algorithms, Lecture Notes in Computer Science, 7288, pp. 119-130. Springer, Berlin Heidelberg.","DOI":"10.1007\/978-3-642-30347-0_14"},{"key":"2016120517351437000_bxw085v1.10","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1137\/0215068","article-title":"Heaps on heaps","volume":"15","author":"Gonnet","year":"1986","journal-title":"SIAM J. Comput."},{"key":"2016120517351437000_bxw085v1.11","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1016\/0196-6774(89)90033-3","article-title":"Building heaps fast","volume":"10","author":"McDiarmid","year":"1989","journal-title":"J. Algorithms"},{"key":"2016120517351437000_bxw085v1.12","doi-asserted-by":"crossref","unstructured":"Li, Z. and Reed, B.A. (2005) Heap building bounds. In Proc. 9th Int. Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 3608, pp. 14\u201323. Springer, Berlin Heidelberg.","DOI":"10.1007\/11534273_3"},{"key":"2016120517351437000_bxw085v1.13","unstructured":"Pasanen, T. (1996) Elementary average case analysis of Floyd's algorithms to construct heaps. TUCS Technical Report No. 64. Turku Centre for Computer Science, Turku."},{"key":"2016120517351437000_bxw085v1.14","doi-asserted-by":"crossref","unstructured":"Frigo, M. , Leiserson, C.E. , Prokop, H. and Ramachandra, S. (1999) Cache-oblivious algorithms. In Proc. 54th Annu. Symp. Foundations of Computer Science, pp. 285\u2013297. IEEE Computer Society, Los Alamitos.","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"2016120517351437000_bxw085v1.15","doi-asserted-by":"crossref","unstructured":"Elmasry, A. , Katajainen, J. and Stenmark, M. (2012) Branch mispredictions don't affect mergesort. In Proc. 11th Int. Symp. Experimental Algorithms, Lecture Notes in Computer Science, Vol. 7276, pp. 160\u2013171. Springer, Berlin Heidelberg.","DOI":"10.1007\/978-3-642-30850-5_15"},{"key":"2016120517351437000_bxw085v1.16","doi-asserted-by":"crossref","unstructured":"Chen, J. , Edelkamp, S. , Elmasry, A. and Katajainen, J. (2012) In-place heap construction with optimized comparisons, moves, and cache misses. In Proc. 37th Int. Symp. Math. Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 7464, pp. 259\u2013270. Springer, Berlin Heidelberg.","DOI":"10.1007\/978-3-642-32589-2_25"},{"key":"2016120517351437000_bxw085v1.17","doi-asserted-by":"publisher","DOI":"10.1145\/359460.359478"},{"key":"2016120517351437000_bxw085v1.18","doi-asserted-by":"crossref","first-page":"1463","DOI":"10.1137\/100785351","article-title":"Rank-pairing heaps","volume":"40","author":"Haeupler","year":"2011","journal-title":"SIAM J. Comput."},{"key":"2016120517351437000_bxw085v1.19","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1007\/BF01990520","article-title":"Weak-heap sort","volume":"33","author":"Dutton","year":"1993","journal-title":"BIT"},{"key":"2016120517351437000_bxw085v1.20","first-page":"238","article-title":"Navigation piles with applications to sorting, priority queues, and priority deques","volume":"10","author":"Katajainen","year":"2003","journal-title":"Nordic J. Comput"},{"key":"2016120517351437000_bxw085v1.21","doi-asserted-by":"crossref","unstructured":"Sanders, P. and Winkel, S. (2004) Super scalar sample sort. In Proc. 12th Annu. Europ. Symp. Algorithms, Lecture Notes in Computer Science, Vol. 3221, pp. 784\u2013796. Springer, Berlin Heidelberg.","DOI":"10.1007\/978-3-540-30140-0_69"},{"key":"2016120517351437000_bxw085v1.22","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0304-3975(93)90364-Y","article-title":"Bottom-Up-Heapsort, a new variant of Heapsort beating, on an average, Quicksort (if n is not very small)","volume":"118","author":"Wegener","year":"1993","journal-title":"Theoret. Comput. Sci"},{"key":"2016120517351437000_bxw085v1.23","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0020-0190(87)90142-6","article-title":"A variant of Heapsort with almost optimal number of comparisons","volume":"24","author":"Carlsson","year":"1987","journal-title":"Inform. Process. Lett"},{"key":"2016120517351437000_bxw085v1.24","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0890-5401(92)90005-Z","article-title":"The worst case complexity of McDiarmid and Reed's variant of Bottom-Up Heapsort is less than n log n + 1.1n.","volume":"97","author":"Wegener","year":"1992","journal-title":"Inform. and Comput."},{"key":"2016120517351437000_bxw085v1.25","unstructured":"Edelkamp, S. , Elmasry, A. and Katajainen, J. (2016) Heap-construction programs. CPH STL Report 2016-1. Department of Computer Science, University of Copenhagen, Copenhagen."},{"key":"2016120517351437000_bxw085v1.26","doi-asserted-by":"crossref","unstructured":"Edelkamp, S. , Elmasry, A. and Katajainen, J. (2016) Optimizing binary heaps. Theory Comput. Syst.? (to appear).","DOI":"10.1007\/s00224-017-9760-2"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/60\/5\/657\/14011339\/bxw085.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,27]],"date-time":"2020-09-27T04:18:44Z","timestamp":1601180324000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article-lookup\/doi\/10.1093\/comjnl\/bxw085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,5]]},"references-count":26,"alternative-id":["10.1093\/comjnl\/bxw085"],"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxw085","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,5]]}}}