{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:13:26Z","timestamp":1725664406500},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540584308"},{"type":"electronic","value":"9783540487890"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58430-7_33","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:03:45Z","timestamp":1330254225000},"page":"371-380","source":"Crossref","is-referenced-by-count":0,"title":["Parallel heap construction using multiple selection"],"prefix":"10.1007","author":[{"given":"Jingsen","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"33_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopocroft, and J. D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Massachusetts, 1974."},{"key":"33_CR2","volume-title":"The Design and Analysis of Parallel Algorithms","author":"S. G. Akl","year":"1989","unstructured":"S. G. Akl: The Design and Analysis of Parallel Algorithms. Prentice-Hall, Englewood Cliffs, New Jersey, 1989."},{"issue":"10","key":"33_CR3","doi-asserted-by":"crossref","first-page":"996","DOI":"10.1145\/6617.6621","volume":"29","author":"M. D. Atkinson","year":"1986","unstructured":"M. D. Atkinson, J.-R. Sack, N. Santoro, and Th. Strothotte: Min-max heaps and generalized priority queues. Communications of the ACM 29 (10) (1986), 996\u20131000.","journal-title":"Communications of the ACM"},{"issue":"1\u20132","key":"33_CR4","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0166-218X(90)90128-Y","volume":"27","author":"Y. Azar","year":"1990","unstructured":"Y. Azar and N. Pippenger: Parallel selection. Discrete Applied Mathematics 27 (1\u20132) (1990), 49\u201358.","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"33_CR5","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan: Time bounds for selection. Journal of Computer and System Sciences 7 (4) (1973), 448\u2013461.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"33_CR6","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R. P. Brent","year":"1974","unstructured":"R. P. Brent: The parallel evaluation of general arithmetic expressions. Journal of the ACM 21 (2) (1974), 201\u2013206.","journal-title":"Journal of the ACM"},{"issue":"1","key":"33_CR7","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0020-0190(87)90033-0","volume":"26","author":"S. Carlsson","year":"1987","unstructured":"S. Carlsson: The deap \u2014 A double-ended heap to implement double-ended priority queues. Information Processing Letters 26 (1) (1987), 33\u201336.","journal-title":"Information Processing Letters"},{"issue":"4","key":"33_CR8","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1142\/S0129626492000453","volume":"2","author":"S. Carlsson","year":"1992","unstructured":"S. Carlsson and J. Chen: Parallel constructions of heaps and min-max heaps. Parallel Processing Letters 2 (4) (1992), 311\u2013320.","journal-title":"Parallel Processing Letters"},{"key":"33_CR9","unstructured":"J. Chen: Constructing priority queues and deques optimally in parallel. Proceedings of the Twelfth World Computer Congress, Volume I, (J. van Leeuwen, Ed.) Madrid, Spain (1992), 275\u2013283."},{"key":"33_CR10","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0020-0190(88)90186-X","volume":"26","author":"R. J. Cole","year":"1987\/88","unstructured":"R. J. Cole: An optimally efficient selection algorithm. Information Processing Letters 26 (1987\/88) 295\u2013299.","journal-title":"Information Processing Letters"},{"key":"33_CR11","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. J. Cole","year":"1988","unstructured":"R. J. Cole: Parallel merge sort. SIAM Journal on Computing 17 (1988) 770\u2013785.","journal-title":"SIAM Journal on Computing"},{"key":"33_CR12","first-page":"334","volume":"81","author":"R. J. Cole","year":"1989","unstructured":"R. J. Cole and U. Vishkin: Faster optimal prefix sums and list ranking. Information and Control 81 (1989) 334\u2013352.","journal-title":"Information and Control"},{"key":"33_CR13","doi-asserted-by":"crossref","unstructured":"P. F. Dietz: Heap construction in the parallel comparison tree model. In: Proceedings of the 3rd Scandinavian Workshop on Algorithm Theory (1992), 140\u2013150.","DOI":"10.1007\/3-540-55706-7_13"},{"issue":"12","key":"33_CR14","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/355588.365103","volume":"7","author":"R. W. Floyd","year":"1964","unstructured":"R. W. Floyd: Algorithm 245 \u2014 Treesort 3. Communications of the ACM 7 (12) (1964), 701.","journal-title":"Communications of the ACM"},{"key":"33_CR15","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1145\/360680.360691","volume":"18","author":"R. W. Floyd","year":"1975","unstructured":"R. W. Floyd and R. L. Rivest: Expected time bounds for selection. Communications of the ACM 18 (1975) 165\u2013172.","journal-title":"Communications of the ACM"},{"issue":"3","key":"33_CR16","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0022-0000(87)90016-X","volume":"35","author":"M. L. Fredman","year":"1987","unstructured":"M. L. Fredman and T. H. Spencer: Refined complexity analysis for heap operations. Journal of Computer and System Sciences 35 (3) (1987), 269\u2013284.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"33_CR17","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1137\/0215068","volume":"15","author":"G. H. Gonnet","year":"1986","unstructured":"G. H. Gonnet and J. I. Munro: Heaps on heaps. SIAM Journal on Computing 15 (4) (1986), 964\u2013971.","journal-title":"SIAM Journal on Computing"},{"key":"33_CR18","volume-title":"The Art of Computer Programming. Vol. 3: Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth: The Art of Computer Programming. Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Massachusetts, 1973."},{"key":"33_CR19","unstructured":"S. Rajasekaran and J. H. Reif: Derivation of randomized sorting and selection algorithms. Technical Report, Aiken Computing Lab., Harvard University, 1987."},{"key":"33_CR20","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0020-0190(91)90154-A","volume":"37","author":"N. S. V. Rao","year":"1991","unstructured":"N. S. V. Rao and W. Zhang: Building heaps in parallel. Information Processing Letters 37 (1991) 355\u2013358.","journal-title":"Information Processing Letters"},{"issue":"2","key":"33_CR21","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF01952680","volume":"29","author":"T. Strothotte","year":"1989","unstructured":"Th. Strothotte, P. Eriksson, and S. Vallner: A note on constructing min-max heaps. BIT 29 (2) (1989), 251\u2013256.","journal-title":"BIT"},{"key":"33_CR22","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"L. G. Valiant","year":"1975","unstructured":"L. G. Valiant: Parallelism in comparison problems. SIAM Journal on Computing 4 (1975) 348\u2013355.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"33_CR23","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J. W. J. Williams","year":"1964","unstructured":"J. W. J. Williams: Algorithm 232: Heapsort. Communications of the ACM 7 (6) (1964), 347\u2013348.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Parallel Processing: CONPAR 94 \u2014 VAPP VI"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58430-7_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T02:11:50Z","timestamp":1640916710000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58430-7_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540584308","9783540487890"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-58430-7_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}