{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:49Z","timestamp":1759637869239,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540646822"},{"type":"electronic","value":"9783540691068"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054364","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T07:43:28Z","timestamp":1149666208000},"page":"158-168","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Comparator networks for binary heap construction"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. Cristina","family":"Pinotti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"Mikl\u00f3s Ajtai, J\u00e1nos Koml\u00f3s, and Endre Szemer\u00e9di. Sorting in c log n parallel steps. Combinatorica, 3:1\u201319, 1983.","journal-title":"Combinatorica"},{"issue":"5","key":"15_CR2","first-page":"99","volume":"5","author":"Vladimir Evgen'evich Alekseev","year":"1969","unstructured":"Vladimir Evgen'evich Alekseev. Sorting algorithms with minimum memory. Kibernetika, 5(5):99\u2013103, 1969.","journal-title":"Kibernetika"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Samuel W. Bent and John W. John. Finding the median requires 2n comparisons. In Proc. 17th Ann. ACM Symp. on Theory of Computing (STOC), pages 213\u2013216, 1985.","DOI":"10.1145\/22145.22169"},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert Endre Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7:448\u2013461, 1973.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR5","first-page":"140","volume-title":"volume 621 of Lecture Notes in Computer Science","author":"P. F. Dietz","year":"1992","unstructured":"Paul F. Dietz. Heap construction in the parallel comparison tree model. In Proc. 3rd Scandinavian Workshop on Algorithm Theory (SWAT), volume 621 of Lecture Notes in Computer Science, pages 140\u2013150. Springer Verlag, Berlin, 1992."},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Paul F. Dietz and Rajeev Raman. Very fast optimal parallel algorithms for heap construction. In Proc. 6th Symposium on Parallel and Distributed Processing, pages 514\u2013521, 1994.","DOI":"10.1109\/SPDP.1994.346128"},{"key":"15_CR7","unstructured":"Dorit Dor and Uri Zwick. Selecting the median. In Proc. 6th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 28\u201337, 1995."},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01300126","volume":"16","author":"D. Dor","year":"1996","unstructured":"Dorit Dor and Uri Zwick. Finding the alpha n-th largest element. Combinatorial, 16:41\u201358, 1996.","journal-title":"Combinatorial"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Dorit Dor and Uri Zwick. Median selection requires (2 + \u03b5)n comparisons. In Proc. 37th Ann. Symp. on Foundations of Computer Science (FOCS), pages 125\u2013134, 1996.","DOI":"10.1109\/SFCS.1996.548471"},{"issue":"12","key":"15_CR10","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/355588.365103","volume":"7","author":"R. W. Floyd","year":"1964","unstructured":"Robert W. Floyd. Algorithm 245: Treesort3. Communications of the ACM, 7(12):701, 1964.","journal-title":"Communications of the ACM"},{"issue":"4","key":"15_CR11","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1137\/S0097539793248329","volume":"25","author":"S. Jimbo","year":"1996","unstructured":"Shuji Jimbo and Akira Maruoka. A method of constructing selection networks with O(log n) depth. SIAM Journal of Computing, 25(4):709\u2013739, 1996.","journal-title":"SIAM Journal of Computing"},{"key":"15_CR12","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"Donald E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, Reading, MA, 1973."},{"issue":"1","key":"15_CR13","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1145\/227595.227693","volume":"43","author":"P. B. Miltersen","year":"1996","unstructured":"Peter Bro Miltersen, Mike Paterson, and Jun Tarui. The asymptotic complexity of merging networks. Journal of the ACM, 43(1):147\u2013165, 1996.","journal-title":"Journal of the ACM"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1109\/71.97899","volume":"2","author":"S. Olariu","year":"1991","unstructured":"Stephan Olariu and Zhaofang Wen. Optimal parallel initialization algorithms for a class of priority queues. IEEE Transactions on Parallel and Distributed Systems, 2:423\u2013429, 1991.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"issue":"5","key":"15_CR15","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1137\/0220054","volume":"20","author":"N. Pippenger","year":"1991","unstructured":"Nicholas Pippenger. Selection networks. SIAM Journal of Computing, 20(5):878\u2013887, 1991.","journal-title":"SIAM Journal of Computing"},{"key":"15_CR16","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/S0022-0000(76)80029-3","volume":"13","author":"A. Sch\u00f6nhage","year":"1976","unstructured":"Arnold Sch\u00f6nhage, Michael S. Paterson, and Nicholas Pippenger. Finding the median. Journal of Computer and System Sciences, 13:184\u2013199, 1976.","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"15_CR17","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J. W. J. Williams","year":"1964","unstructured":"John William Joseph Williams. Algorithm 232: Heapsort. Communications of the ACM, 7(6):347\u2013348, 1964.","journal-title":"Communications of the ACM"},{"key":"15_CR18","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1145\/321958.321976","volume":"23","author":"A. C. Yao","year":"1976","unstructured":"Andrew C. Yao and Frances F. Yao. Lower bounds on merging networks. Journal of the ACM, 23:566\u2013571, 1976.","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'98"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T07:20:34Z","timestamp":1736407234000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0054364"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540646822","9783540691068"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/bfb0054364","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"26 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}