{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T08:42:41Z","timestamp":1725698561895},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325885"},{"type":"electronic","value":"9783642325892"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32589-2_25","type":"book-chapter","created":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T08:44:32Z","timestamp":1343810672000},"page":"259-270","source":"Crossref","is-referenced-by-count":7,"title":["In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses"],"prefix":"10.1007","author":[{"given":"Jingsen","family":"Chen","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Edelkamp","sequence":"additional","affiliation":[]},{"given":"Amr","family":"Elmasry","sequence":"additional","affiliation":[]},{"given":"Jyrki","family":"Katajainen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/351827.384257","volume":"5","author":"J. Bojesen","year":"2000","unstructured":"Bojesen, J., Katajainen, J., Spork, M.: Performance engineering case study: Heap construction. ACM J. Exp. Algorithmics\u00a05, Article 15 (2000)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"4","key":"25_CR2","doi-asserted-by":"publisher","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.\u00a024(4), 247\u2013250 (1987)","journal-title":"Inform. Process. Lett."},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/3-540-57568-5_241","volume-title":"Algorithms and Computation","author":"J. Chen","year":"1993","unstructured":"Chen, J.: A Framework for Constructing Heap-Like Structures in-Place. In: Ng, K.W., Balasubramanian, N.V., Raghavan, P., Chin, F.Y.L. (eds.) ISAAC 1993. LNCS, vol.\u00a0762, pp. 118\u2013127. Springer, Heidelberg (1993)"},{"key":"25_CR4","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"issue":"3","key":"25_CR5","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/BF01990520","volume":"33","author":"R.D. Dutton","year":"1993","unstructured":"Dutton, R.D.: Weak-heap sort. BIT\u00a033(3), 372\u2013381 (1993)","journal-title":"BIT"},{"issue":"12","key":"25_CR6","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/355588.365103","volume":"7","author":"R.W. Floyd","year":"1964","unstructured":"Floyd, R.W.: Algorithm 245: Treesort 3. Commun. ACM\u00a07(12), 701 (1964)","journal-title":"Commun. ACM"},{"key":"25_CR7","first-page":"285","volume-title":"40th Annual Symposium on Foundations of Computer Science","author":"M. Frigo","year":"1999","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandra, S.: Cache-oblivious algorithms. In: 40th Annual Symposium on Foundations of Computer Science, pp. 285\u2013297. IEEE Computer Society, Los Alamitos (1999)"},{"issue":"4","key":"25_CR8","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1137\/0215068","volume":"15","author":"G.H. Gonnet","year":"1986","unstructured":"Gonnet, G.H., Munro, J.I.: Heaps on heaps. SIAM J. Comput.\u00a015(4), 964\u2013971 (1986)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"25_CR9","first-page":"238","volume":"10","author":"J. Katajainen","year":"2003","unstructured":"Katajainen, J., Vitale, F.: Navigation piles with applications to sorting, priority queues, and priority deques. Nordic J. Comput.\u00a010(3), 238\u2013262 (2003)","journal-title":"Nordic J. Comput."},{"key":"25_CR10","first-page":"744","volume":"10","author":"M.A. Kronrod","year":"1969","unstructured":"Kronrod, M.A.: Optimal ordering algorithm without operational field. Soviet Math. Dokl.\u00a010, 744\u2013746 (1969)","journal-title":"Soviet Math. Dokl."},{"key":"25_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/11534273_3","volume-title":"Algorithms and Data Structures","author":"Z. Li","year":"2005","unstructured":"Li, Z., Reed, B.A.: Heap Building Bounds. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 14\u201323. Springer, Heidelberg (2005)"},{"issue":"3","key":"25_CR12","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1016\/0196-6774(89)90033-3","volume":"10","author":"C.J.H. McDiarmid","year":"1989","unstructured":"McDiarmid, C.J.H., Reed, B.A.: Building heaps fast. J. Algorithms\u00a010(3), 352\u2013365 (1989)","journal-title":"J. Algorithms"},{"issue":"4","key":"25_CR13","doi-asserted-by":"publisher","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\u00a021(4), 309\u2013315 (1978)","journal-title":"Commun. ACM"},{"issue":"1","key":"25_CR14","doi-asserted-by":"publisher","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.\u00a0118(1), 81\u201398 (1993)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"25_CR15","doi-asserted-by":"publisher","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 nlogn\u2009+\u20091. 1n. Inform. and Comput.\u00a097(1), 86\u201396 (1992)","journal-title":"Inform. and Comput."},{"issue":"6","key":"25_CR16","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J.W.J. Williams","year":"1964","unstructured":"Williams, J.W.J.: Algorithm 232: Heapsort. Commun. ACM\u00a07(6), 347\u2013348 (1964)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32589-2_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,25]],"date-time":"2022-01-25T02:07:42Z","timestamp":1643076462000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32589-2_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325885","9783642325892"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32589-2_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}