{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T20:31:56Z","timestamp":1743107516040,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031757822"},{"type":"electronic","value":"9783031757839"}],"license":[{"start":{"date-parts":[[2024,11,13]],"date-time":"2024-11-13T00:00:00Z","timestamp":1731456000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,13]],"date-time":"2024-11-13T00:00:00Z","timestamp":1731456000000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-75783-9_3","type":"book-chapter","created":{"date-parts":[[2024,11,12]],"date-time":"2024-11-12T06:27:11Z","timestamp":1731392831000},"page":"73-84","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Amortized Analysis of\u00a0Leftist Heaps"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6273-8930","authenticated-orcid":false,"given":"Berry","family":"Schoenmakers","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,11,13]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Batz, K., Kaminski, B.L., Katoen, J.-P., Matheja, C., Verscht. L.: A calculus for amortized expected runtimes. Proce. ACM Program. Lang. 7(POPL), 1957\u20131986 (2023)","DOI":"10.1145\/3571260"},{"key":"3_CR2","doi-asserted-by":"publisher","unstructured":"Brodal, G.S.: A Survey on Priority Queues. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Space-Efficient Data Structures, Streams, and Algorithms. LNCS, vol. 8066, pp. 150\u2013163. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40273-9_11","DOI":"10.1007\/978-3-642-40273-9_11"},{"key":"3_CR3","unstructured":"Crane, C.A.: Linear Lists and Priority Queues as Balanced Binary Trees. PhD thesis, Computer Science, Stanford University, CA (1972)"},{"key":"3_CR4","doi-asserted-by":"publisher","unstructured":"Cho, S., Sahni, S.: Weight biased leftist trees and modified skip lists. In: International Computing and Combinatorics Conference (COCOON \u201996), LNCS 1090, pp. 361\u2013370. Springer (1996). https:\/\/doi.org\/10.1007\/3-540-61332-3_170","DOI":"10.1007\/3-540-61332-3_170"},{"key":"3_CR5","doi-asserted-by":"publisher","unstructured":"Gambin, A., Malinowski, A.: Randomized meldable priority queues. In: SOFSEM \u201998: Theory and Practice of Informatics, LNCS 1521, pp. 344\u2013349. Springer (1998). https:\/\/doi.org\/10.1007\/3-540-49477-4_26","DOI":"10.1007\/3-540-49477-4_26"},{"key":"3_CR6","unstructured":"Hofstadter, D.R.: G\u00f6del, Escher, Bach: an Eternal Golden Braid, Basic Books (1979)"},{"issue":"1","key":"3_CR7","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1145\/63238.63249","volume":"32","author":"DW Jones","year":"1989","unstructured":"Jones, D.W.: Concurrent operations on priority queues. Commun. ACM 32(1), 132\u2013137 (1989)","journal-title":"Commun. ACM"},{"key":"3_CR8","unstructured":"Knuth, D.E.: The Art of Computer Programming (Vol. 3: Sorting and Searching). Addison Wesley, Reading, MA, 2nd edition (1998)"},{"issue":"5","key":"3_CR9","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0020-0190(91)90218-7","volume":"37","author":"A Kaldewaij","year":"1991","unstructured":"Kaldewaij, A., Schoenmakers, B.: The derivation of a tighter bound for top-down skew heaps. Inf. Process. Lett. 37(5), 265\u2013271 (1991)","journal-title":"Inf. Process. Lett."},{"key":"3_CR10","unstructured":"Katoen, J.-P., Schoenmakers, B.: A parallel program for the recognition of P-invariant segments. In: Proceedings of the International Workshop Algorithms and Parallel VLSI Architectures II, pp. 79\u201384. Elsevier (1991)"},{"issue":"2","key":"3_CR11","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0167-6423(96)00009-3","volume":"27","author":"J-P Katoen","year":"1996","unstructured":"Katoen, J.-P., Schoenmakers, B.: Systolic arrays for the recognition of permutation-invariant segments. Sci. Comput. Program. 27(2), 119\u2013137 (1996)","journal-title":"Sci. Comput. Program."},{"key":"3_CR12","doi-asserted-by":"publisher","unstructured":"Leutgeb, L., Moser, G., Zuleger, F.: ATLAS: automated amortised complexity analysis of self-adjusting data structures. In: Silva, A., Leino, K.R.M. (eds.) CAV 2021. LNCS, vol. 12760, pp. 99\u2013122. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-81688-9_5","DOI":"10.1007\/978-3-030-81688-9_5"},{"key":"3_CR13","doi-asserted-by":"publisher","unstructured":"Leutgeb, L., Moser, G., Zuleger, F.: Automated expected amortised cost analysis of probabilistic data structures. In: Computer Aided Verification (CAV 2022), LNCS 13372, pp. 70\u201391. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-13188-2_4","DOI":"10.1007\/978-3-031-13188-2_4"},{"issue":"1","key":"3_CR14","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1137\/0215002","volume":"15","author":"K Mehlhorn","year":"1986","unstructured":"Mehlhorn, K., Tsakalidis, A.: An amortized analysis of insertions into AVL-trees. SIAM J. Comput. 15(1), 22\u201333 (1986)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"3_CR15","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s10817-018-9459-3","volume":"62","author":"T Nipkow","year":"2019","unstructured":"Nipkow, T., Brinkop, H.: Amortized complexity verified. J. Autom. Reason. 62(3), 367\u2013391 (2019)","journal-title":"J. Autom. Reason."},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Okasaki, C.: Purely Functional Data Structures, Cambridge University Press (1999)","DOI":"10.1017\/CBO9780511530104"},{"key":"3_CR17","unstructured":"Schoenmakers, B.: Data Structures and Amortized Complexity in a Functional Setting. PhD thesis, Math & CS, TU Eindhoven, Netherlands (1992)"},{"issue":"1","key":"3_CR18","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0020-0190(93)90249-9","volume":"45","author":"B Schoenmakers","year":"1993","unstructured":"Schoenmakers, B.: A systematic analysis of splaying. Inf. Process. Lett. 45(1), 41\u201350 (1993)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"3_CR19","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0020-0190(97)00028-8","volume":"61","author":"B Schoenmakers","year":"1997","unstructured":"Schoenmakers, B.: A tight lower bound for top-down skew heaps. Inf. Process. Lett. 61(5), 279\u2013284 (1997)","journal-title":"Inf. Process. Lett."},{"key":"3_CR20","doi-asserted-by":"publisher","unstructured":"Sleator, D.D.: Data structures and terminating Petri nets. In: Simon, I. (ed.) LATIN 1992. LNCS, vol. 583, pp. 488\u2013497. Springer, Heidelberg (1992). https:\/\/doi.org\/10.1007\/BFb0023850","DOI":"10.1007\/BFb0023850"},{"issue":"3","key":"3_CR21","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652\u2013686 (1985)","journal-title":"J. ACM"},{"issue":"3","key":"3_CR22","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1137\/0215004","volume":"15","author":"DD Sleator","year":"1986","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting heaps. SIAM J. Comput. 15(3), 52\u201369 (1986)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"3_CR23","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Amortized computational complexity. SIAM J. Algebraic Discrete Methods 6(2), 306\u2013318 (1985)","journal-title":"SIAM J. Algebraic Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","Principles of Verification: Cycling the Probabilistic Landscape"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-75783-9_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,12]],"date-time":"2024-11-12T07:02:16Z","timestamp":1731394936000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-75783-9_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,13]]},"ISBN":["9783031757822","9783031757839"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-75783-9_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,11,13]]},"assertion":[{"value":"13 November 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}