{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,3]],"date-time":"2023-05-03T23:11:10Z","timestamp":1683155470417},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1996,5,1]],"date-time":"1996-05-01T00:00:00Z","timestamp":830908800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1996,5]]},"DOI":"10.1007\/bf01955045","type":"journal-article","created":{"date-parts":[[2005,7,31]],"date-time":"2005-07-31T22:43:50Z","timestamp":1122849830000},"page":"467-480","source":"Crossref","is-referenced-by-count":3,"title":["Recurrence relations on heaps"],"prefix":"10.1007","volume":"15","author":[{"given":"R.","family":"Sprugnoli","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF01955045_CR1","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.Comm. ACM,29 (1986), 996\u20131000.","journal-title":"Comm. ACM"},{"key":"BF01955045_CR2","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1016\/0196-6774(85)90028-8","volume":"6","author":"B. Bollobas","year":"1985","unstructured":"B. Bollobas and I. Simon. Repeated random insertion into a priority queue.J. Algorithms,6 (1985), 466\u2013477.","journal-title":"J. Algorithms"},{"key":"BF01955045_CR3","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0020-0190(87)90142-6","volume":"24","author":"S. Carlsson","year":"1987","unstructured":"S. Carlsson. A variant of heapsort with almost optimal number of comparisons.Inform. Process. Lett.,24 (1987), 247\u2013250.","journal-title":"Inform. Process. Lett."},{"key":"BF01955045_CR4","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0020-0190(87)90033-0","volume":"26","author":"S. Carlsson","year":"1987\u20131988","unstructured":"S. Carlsson. The Deap \u2014 a double-ended heap to implement double-ended priority queues.Inform. Process. Letters,26 (1987\u20131988), 33\u201336.","journal-title":"Inform. Process. Letters"},{"key":"BF01955045_CR5","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01937350","volume":"27","author":"S. Carlsson","year":"1987","unstructured":"S. Carlsson. Average-case results on heapsort.Bit,27 (1987), 2\u201317.","journal-title":"Bit"},{"key":"BF01955045_CR6","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0020-0190(89)90094-X","volume":"31","author":"S. Carlsson","year":"1989","unstructured":"S. Carlsson and J. Chen. A note on the construction of the data structure \u201cDeap\u201d.Inform. Process. Lett.,31 (1989), 315\u2013317.","journal-title":"Inform. Process. Lett."},{"key":"BF01955045_CR7","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01941462","volume":"21","author":"E.-E. Doberkat","year":"1981","unstructured":"E.-E. Doberkat. Inserting a new element into a heap.Bit,21 (1981), 255\u2013269.","journal-title":"Bit"},{"key":"BF01955045_CR8","first-page":"245","volume":"17","author":"E.-E. Doberkat","year":"1982","unstructured":"E.-E. Doberkat. Deleting the root of a heap.Acta Inform.,17 (1982), 245\u2013265.","journal-title":"Acta Inform."},{"key":"BF01955045_CR9","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1016\/S0019-9958(84)80053-4","volume":"61","author":"E.-E. Doberkat","year":"1984","unstructured":"E.-E. Doberkat. An average case analysis of Floyd's algorithm to construct heaps.Inform. and Control,61 (1984), 114\u2013131.","journal-title":"Inform. and Control"},{"key":"BF01955045_CR10","first-page":"43","volume-title":"Lecture Notes in Computer Science, Vol. 308","author":"L. Draws","year":"1988","unstructured":"L. Draws, P. Eriksson, E. Forslund, L. H\u00f6glund, S. Vallner, and Th. Strothotte. Two new algorithms for constructing Min-Max heaps.Proc. Scand. Workshop on Algorithm Theory, 1988, Lecture Notes in Computer Science, Vol. 308, Springer-Verlag, Berlin, pp. 43\u201350."},{"key":"BF01955045_CR11","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 254, treesort 3.Comm. ACM,7 (1964), 701.","journal-title":"Comm. ACM"},{"key":"BF01955045_CR12","doi-asserted-by":"crossref","unstructured":"J. Francon, G. Viennot, and J. Vuillemin. Description and analysis of an efficient priority queue representation.Proc. 19th Ann. Symp. on Foundations of Computer Science, Ann Arbor, MI, 1978.","DOI":"10.1109\/SFCS.1978.13"},{"key":"BF01955045_CR13","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0020-0190(88)90101-9","volume":"27","author":"G. M. Frieze","year":"1988","unstructured":"G. M. Frieze. On the random construction of heaps.Inform. Process. Lett.,27 (1988), 103\u2013109.","journal-title":"Inform. Process. Lett."},{"key":"BF01955045_CR14","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 J. Comput.,15 (1986), 964\u2013971.","journal-title":"SIAM J. Comput."},{"key":"BF01955045_CR15","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF01933726","volume":"27","author":"A. Hasham","year":"1987","unstructured":"A. Hasham and J.-H. Sack. Bounds for Min-Max heaps.Bit,27 (1987), 315\u2013323.","journal-title":"Bit"},{"key":"BF01955045_CR16","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/0196-6774(91)90027-V","volume":"12","author":"R. Hayward","year":"1991","unstructured":"R. Hayward and C. McDiarmid. Average case analysis of heap building by repeated insertions.J. Algorithms,12 (1991), 126\u2013153.","journal-title":"J. Algorithms"},{"key":"BF01955045_CR17","unstructured":"H. K. Hwang and J.-M. Steyaert. On the number of heaps and the cost of heap construction,Theoret. Comput. Sci., submitted."},{"key":"BF01955045_CR18","volume-title":"The Art of Computer Programming, Vol. 3","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth.The Art of Computer Programming, Vol. 3. Addison-Wesley, Reading, MA, 1973."},{"key":"BF01955045_CR19","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1016\/0196-6774(89)90033-3","volume":"10","author":"C. McDiarmid","year":"1989","unstructured":"C. McDiarmid and B. A. Reed. Building heaps fast.J. Algorithms,10 (1989), 352\u2013365.","journal-title":"J. Algorithms"},{"key":"BF01955045_CR20","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1109\/TSE.1975.6312854","volume":"3","author":"T. Porter","year":"1975","unstructured":"T. Porter and I. Simon. Random insertion into a priority queue structure.IEEE Trans. Software Engrg.,3 (1975), 292\u2013298.","journal-title":"IEEE Trans. Software Engrg."},{"key":"BF01955045_CR21","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF00264229","volume":"22","author":"J.-H. Sack","year":"1985","unstructured":"J.-H. Sack and Th. Strothotte. An algorithm for merging heaps.Acta Inform.,22 (1985), 171\u2013186.","journal-title":"Acta Inform."},{"key":"BF01955045_CR22","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1006\/jagm.1993.1031","volume":"15","author":"R. Schaffer","year":"1993","unstructured":"R. Schaffer and R. Sedgewick. The analysis of heapsort.J. Algorithms,15 (1993) 76\u2013100.","journal-title":"J. Algorithms"},{"key":"BF01955045_CR23","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1145\/359460.359478","volume":"21","author":"J. Vuillemin","year":"1978","unstructured":"J. Vuillemin. A data structure for manipulating priority queues.Comm. ACM,21 (1978), 304\u2013315.","journal-title":"Comm. ACM"},{"key":"BF01955045_CR24","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1109\/32.29490","volume":"15","author":"I. Wegner","year":"1989","unstructured":"I. Wegner and J. I. Teuhola. The external heapsort.IEEE Trans. Software Engrg.,15 (1989), 917\u2013925.","journal-title":"IEEE Trans. Software Engrg."},{"key":"BF01955045_CR25","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.Comm. ACM,7 (1964), 347\u2013348.","journal-title":"Comm. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01955045.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01955045\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01955045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,3]],"date-time":"2023-05-03T22:56:04Z","timestamp":1683154564000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01955045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,5]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1996,5]]}},"alternative-id":["BF01955045"],"URL":"https:\/\/doi.org\/10.1007\/bf01955045","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,5]]}}}