{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T05:47:52Z","timestamp":1757310472367,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_116","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:36:52Z","timestamp":1330292212000},"page":"4-15","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["The randomized complexity of maintaining the minimum"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shiva","family":"Chaudhuri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaikumar","family":"Radhakrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0020-0190(81)90031-4","volume":"13","author":"M. J. Atallah","year":"1981","unstructured":"Mikhail J. Atallah and S. Rao Kosaraju. An adversary-based lower bound for sorting. Information Processing Letters, 13:55\u201357, 1981.","journal-title":"Information Processing Letters"},{"key":"2_CR2","first-page":"282","volume-title":"volume 955 of Lecture Notes in Computer Science","author":"G. S. Brodal","year":"1995","unstructured":"Gerth St\u00f8lting Brodal. Fast meldable priority queues. In Proc. 4th Workshop on Algorithms and Data Structures (WADS), volume 955 of Lecture Notes in Computer Science, pages 282\u2013290. Springer Verlag, Berlin, 1995."},{"key":"2_CR3","first-page":"1","volume-title":"volume 318 of Lecture Notes in Computer Science","author":"S. Carlsson","year":"1988","unstructured":"Svante Carlsson, Patricio V. Poblete, and J. Ian Munro. An implicit binomial queue with constant insertion time. In Proc. 1st Scandinavian Workshop on Algorithm Theory (SWAT), volume 318 of Lecture Notes in Computer Science, pages 1\u201313. Springer Verlag, Berlin, 1988."},{"issue":"11","key":"2_CR4","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1145\/50087.50096","volume":"31","author":"J. R. Driscoll","year":"1988","unstructured":"James R. Driscoll, Harold N. Gabow, Ruth Shrairman, and Robert E. Tarjan. Relaxed heaps: An alternative to fibonacci heaps with applications to parallel computation. Communications of the ACM, 31(11):1343\u20131354, 1988.","journal-title":"Communications of the ACM"},{"key":"2_CR5","first-page":"138","volume-title":"volume 762 of Lecture Notes in Computer Science","author":"R. Fleischer","year":"1993","unstructured":"Rudolf Fleischer. A simple balanced search tree with O(1) worst-case update time. In Algorithms and Computation: 4th International Symposium, ISAAC '93, volume 762 of Lecture Notes in Computer Science, pages 138\u2013146. Springer Verlag, Berlin, 1993."},{"key":"2_CR6","volume-title":"Inequalities","author":"G. H. Hardy","year":"1952","unstructured":"G. H. Hardy, J. E. Littlewood, and G. Polya. Inequalities. Cambridge University Press, Cambridge, 1952."},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF00299635","volume":"26","author":"C. Levcopoulos","year":"1988","unstructured":"Christos Levcopoulos and Mark H. Overmars. A balanced search tree with O(1) worst-case update time. ACTA Informatica, 26:269\u2013277, 1988.","journal-title":"ACTA Informatica"},{"issue":"6","key":"2_CR8","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):347\u2013348, 1964.","journal-title":"Communications of the ACM"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"A. C-C. Yao. Probabilistic computations: Towards a unified measure of complexity. In Proc. of the 17th Symp. on Found. of Comp. Sci., 222\u2013227, 1977.","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_116","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:18:31Z","timestamp":1742599111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_116","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"7 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}