{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T01:23:22Z","timestamp":1725758602728},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642452772"},{"type":"electronic","value":"9783642452789"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45278-9_1","type":"book-chapter","created":{"date-parts":[[2013,11,25]],"date-time":"2013-11-25T15:35:18Z","timestamp":1385393718000},"page":"1-6","source":"Crossref","is-referenced-by-count":0,"title":["Weak Heaps and Friends: Recent Developments"],"prefix":"10.1007","author":[{"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"}]},{"given":"Armin","family":"Wei\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/978-3-642-13193-6_36","volume-title":"Experimental Algorithms","author":"A. Bruun","year":"2010","unstructured":"Bruun, A., Edelkamp, S., Katajainen, J., Rasmussen, J.: Policy-based benchmarking of weak heaps and their relatives. In: Festa, P. (ed.) SEA 2010. LNCS, vol.\u00a06049, pp. 424\u2013435. Springer, Heidelberg (2010)"},{"issue":"1","key":"1_CR2","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0304-3975(01)00288-2","volume":"285","author":"D. Cantone","year":"2002","unstructured":"Cantone, D., Cinotti, G.: QuickHeapsort, an efficient mix of classical sorting algorithms. Theoret. Comput. Sci.\u00a0285(1), 25\u201342 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-3-642-32589-2_25","volume-title":"Mathematical Foundations of Computer Science 2012","author":"J. Chen","year":"2012","unstructured":"Chen, J., Edelkamp, S., Elmasry, A., Katajainen, J.: In-place heap construction with optimized comparisons, moves, and cache misses. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 259\u2013270. Springer, Heidelberg (2012)"},{"key":"1_CR4","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press (2009)"},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-38536-0_3","volume-title":"Computer Science \u2013 Theory and Applications","author":"V. Diekert","year":"2013","unstructured":"Diekert, V., Wei\u00df, A.: QuickHeapsort: Modifications and improved analysis. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol.\u00a07913, pp. 24\u201335. Springer, Heidelberg (2013)"},{"issue":"11","key":"1_CR6","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1145\/50087.50096","volume":"31","author":"J.R. 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\u00a031(11), 1343\u20131354 (1988)","journal-title":"Commun. ACM"},{"issue":"3","key":"1_CR7","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"},{"key":"1_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-642-25011-8_16","volume-title":"Combinatorial Algorithms","author":"S. Edelkamp","year":"2011","unstructured":"Edelkamp, S., Elmasry, A., Katajainen, J.: Two constant-factor-optimal realizations of adaptive heapsort. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2011. LNCS, vol.\u00a07056, pp. 195\u2013208. Springer, Heidelberg (2011)"},{"key":"1_CR9","first-page":"103","volume-title":"CATS 2012, Conferences in Research and Practice in Information Technology","author":"S. Edelkamp","year":"2012","unstructured":"Edelkamp, S., Elmasry, A., Katajainen, J.: The weak-heap family of priority queues in theory and praxis. In: Mestre, J. (ed.) CATS 2012, Conferences in Research and Practice in Information Technology, vol.\u00a0128, pp. 103\u2013112. Australian Computer Society, Inc., Adelaide (2012)"},{"key":"1_CR10","doi-asserted-by":"publisher","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\u00a016, 187\u2013205 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/978-3-642-35926-2_27","volume-title":"IWOCA 2012","author":"S. Edelkamp","year":"2012","unstructured":"Edelkamp, S., Elmasry, A., Katajainen, J.: A catalogue of algorithms for building weak heaps. In: Smyth, B. (ed.) IWOCA 2012. LNCS, vol.\u00a07643, pp. 249\u2013262. Springer, Heidelberg (2012)"},{"key":"1_CR12","unstructured":"Edelkamp, S., Elmasry, A., Katajainen, J.: Weak heaps engineered. J. Discrete Algorithms (to appear)"},{"key":"1_CR13","unstructured":"Edelkamp, S., Elmasry, A., Katajainen, J.: Optimal in-place heaps (submitted)"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Stiegeler, P.: Implementing Heapsort with n logn\u2009\u2212\u20090.9 n and Quicksort with n logn\u2009+\u20090.2 n comparisons. ACM J. Exp. Algorithmics\u00a07, Article 5 (2002)","DOI":"10.1145\/944618.944623"},{"key":"1_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/3-540-46541-3_21","volume-title":"STACS 2000","author":"S. Edelkamp","year":"2000","unstructured":"Edelkamp, S., Wegener, I.: On the performance of Weak-Heapsort. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 254\u2013266. Springer, Heidelberg (2000)"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Weiss, A.: QuickXsort: Efficient sorting with n log n \u2212 1.399n+o(n) comparisons on average. E-print arXiv:1307.3033, arXiv.org, Ithaca (2013)","DOI":"10.1007\/978-3-319-06686-8_11"},{"issue":"1","key":"1_CR17","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s00236-007-0061-0","volume":"45","author":"A. Elmasry","year":"2008","unstructured":"Elmasry, A., Fredman, M.L.: Adaptive sorting: An information theoretic perspective. Acta Inform.\u00a045(1), 33\u201342 (2008)","journal-title":"Acta Inform."},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Elmasry, A., Hammad, A.: Inversion-sensitive sorting algorithms in practice. ACM J. Exp. Algorithmics\u00a013, Article 1.11 (2009)","DOI":"10.1145\/1412228.1455267"},{"issue":"1","key":"1_CR19","doi-asserted-by":"crossref","first-page":"14","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\u00a05(1), Article 14 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"1_CR20","unstructured":"Elmasry, A., Katajainen, J.: Towards ultimate binary heaps. CPH STL Report 2013-3, Department of Computer Science, University of Copenhagen, Copenhagen (2013)"},{"issue":"4","key":"1_CR21","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."},{"key":"1_CR22","first-page":"87","volume-title":"CATS 2012, Australian Computer Science Communications","author":"J. Katajainen","year":"1998","unstructured":"Katajainen, J.: The ultimate heapsort. In: Lin, X. (ed.) CATS 2012, Australian Computer Science Communications, vol.\u00a020, pp. 87\u201396. Springer-Verlag Singapore Pte. Ltd., Singapore (1998)"},{"issue":"3","key":"1_CR23","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":"1_CR24","volume-title":"Sorting and Searching, The Art of Computer Programming","author":"D.E. Knuth","year":"1998","unstructured":"Knuth, D.E.: Sorting and Searching, The Art of Computer Programming, 2nd edn., vol.\u00a03. Addison Wesley Longman, Reading (1998)","edition":"2"},{"issue":"3","key":"1_CR25","doi-asserted-by":"publisher","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\u00a014(3), 395\u2013413 (1993)","journal-title":"J. Algorithms"},{"issue":"3","key":"1_CR26","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":"8","key":"1_CR27","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1002\/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#","volume":"27","author":"D.R. Musser","year":"1997","unstructured":"Musser, D.R.: Introspective sorting and selection algorithms. Software Pract. Exper.\u00a027(8), 983\u2013993 (1997)","journal-title":"Software Pract. Exper."},{"issue":"4","key":"1_CR28","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":"1_CR29","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":"6","key":"1_CR30","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","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45278-9_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T11:24:06Z","timestamp":1647516246000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45278-9_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642452772","9783642452789"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45278-9_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}