{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T11:40:24Z","timestamp":1683286824715},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1992,3,1]],"date-time":"1992-03-01T00:00:00Z","timestamp":699408000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[1992,3]]},"DOI":"10.1007\/bf02238646","type":"journal-article","created":{"date-parts":[[2005,11,14]],"date-time":"2005-11-14T17:25:38Z","timestamp":1131989138000},"page":"1-9","source":"Crossref","is-referenced-by-count":3,"title":["Best case lower bounds for Heapsort","Untere Schranken von Heapsort f\u00fcr den besten Fall"],"prefix":"10.1007","volume":"49","author":[{"given":"Y.","family":"Ding","sequence":"first","affiliation":[]},{"given":"M. A.","family":"Weiss","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02238646_CR1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01937350","volume":"27","author":"S. Carlsson","year":"1987","unstructured":"[Ca87a] Carlsson, S.: Average-case results on heapsort. BIT27, 2 (1987).","journal-title":"BIT"},{"key":"BF02238646_CR2","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1016\/0020-0190(87)90142-6","volume":"24","author":"S. Carlsson","year":"1987","unstructured":"[Ca87b] Carlsson, S.: A variant of heapsort with almost optimal number of comparisons. Information Processing Letters24, 4 (1987).","journal-title":"Information Processing Letters"},{"key":"BF02238646_CR3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0020-0190(91)90144-7","volume":"37","author":"S. Carlsson","year":"1991","unstructured":"[Ca91] Carlsson, S.: An optimal algorithm for deleting the root of a heap. Information Processing Letters37, 2 (1991).","journal-title":"Information Processing Letters"},{"key":"BF02238646_CR4","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(84)80053-4","volume":"61","author":"E. Doberkat","year":"1984","unstructured":"[Do84] Doberkat, E.: An average case analysis of Floyd's algorithm to construct heaps. Information and Control61, 2 (1984).","journal-title":"Information and Control"},{"key":"BF02238646_CR5","unstructured":"[DW91] Ding, Y., Weiss, M.: On heapsort algorithms that are good in both worst-case and averagecase, Tech. Report, School of Computer Science, Florida International University, Feb. 1991."},{"key":"BF02238646_CR6","first-page":"12","volume":"7","author":"R. Floyd","year":"1964","unstructured":"[Fl64] Floyd, R.: Algorithm 245: Treesort. Comm. ACM7, 12 (1964).","journal-title":"Comm. ACM"},{"key":"BF02238646_CR7","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0020-0190(88)90101-9","volume":"27","author":"A. Frieze","year":"1988","unstructured":"[Fr88] Frieze, A.: On the random construction of heaps. Information Processing Letters27, 2 (1988).","journal-title":"Information Processing Letters"},{"key":"BF02238646_CR8","doi-asserted-by":"crossref","unstructured":"[FSU91] Fleischer, R., Sinha, B., Uhrig, C.: A lower bound for the worst case of bottom-up-heapsort, personal communication, Jan. 1991.","DOI":"10.1007\/3-540-54945-5_69"},{"key":"BF02238646_CR9","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1137\/0215068","volume":"15","author":"G. Gonnet","year":"1986","unstructured":"[GM86] Gonnet, G., Munro, J.: Heaps on heaps. SIAM J. Comput.15 4 (1986).","journal-title":"SIAM J. Comput."},{"key":"BF02238646_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(91)90027-V","volume":"12","author":"R. Hayward","year":"1991","unstructured":"[Ha91] Hayward, R.: Average case analysis of heap building by repeated insertion. J. Algorithms12, 1 (1991).","journal-title":"J. Algorithms"},{"key":"BF02238646_CR11","volume-title":"The art of computer programming, Vol. 3","author":"D. Knuth","year":"1973","unstructured":"[Kn73] Knuth, D.: The art of computer programming, Vol. 3. Reading, MA: Addison-Wesley 1973."},{"key":"BF02238646_CR12","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0196-6774(89)90033-3","volume":"10","author":"C. McDiarmid","year":"1989","unstructured":"[MR89] McDiarmid, C., Reed, B.: Building heaps fast. J. Algorithms10, 3 (1989).","journal-title":"J. Algorithms"},{"key":"BF02238646_CR13","first-page":"3","volume":"1","author":"T. Porter","year":"1975","unstructured":"[PS75] Porter, T., Simon, I.: Random insertion into a priority queue structure. IEEE Trans. Software EngineeringSE-1, 3 (1975).","journal-title":"IEEE Trans. Software Engineering SE"},{"key":"BF02238646_CR14","series-title":"MFCS'90, Lecture Notes in Computer Science","volume-title":"Bottom-up-heapsort, a new variant of heapsort beating on avergage quicksort (ifn is not very small)","author":"I. Wegener","year":"1990","unstructured":"[We90] Wegener, I.: Bottom-up-heapsort, a new variant of heapsort beating on avergage quicksort (ifn is not very small). Berlin, Heidelberg, New York: Springer 1990 (MFCS'90, Lecture Notes in Computer Science 452)."},{"key":"BF02238646_CR15","first-page":"6","volume":"7","author":"J. Williams","year":"1964","unstructured":"[Wi64] Williams, J.: Algorithm 232: Heapsort. Comm. ACM7, 6 (1964).","journal-title":"Comm. ACM"},{"key":"BF02238646_CR16","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1093\/comjnl\/33.3.281","volume":"33","author":"G. Xunrang","year":"1990","unstructured":"[XY90] Xunrang, G., Yuzhang, Z.: A new heapsort algorithm and the analysis of its complexity. The Computer Journal33, 3 (1990).","journal-title":"The Computer Journal"}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02238646.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02238646\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02238646","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T11:20:10Z","timestamp":1683285610000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02238646"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,3]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1992,3]]}},"alternative-id":["BF02238646"],"URL":"https:\/\/doi.org\/10.1007\/bf02238646","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"value":"0010-485X","type":"print"},{"value":"1436-5057","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,3]]}}}