{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T06:38:55Z","timestamp":1784011135534,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662476710","type":"print"},{"value":"9783662476727","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_72","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"886-897","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Replacing Mark Bits with Randomness in Fibonacci Heaps"],"prefix":"10.1007","author":[{"given":"Jerry","family":"Li","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Peebles","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"72_CR1","first-page":"263","volume":"3","author":"GM Adelson-Velskii","year":"1962","unstructured":"Adelson-Velskii, G.M., Landis, E.M.: An algorithm for the organization of information. Dokl. Akad. Nauk SSSR 3, 263\u2013266 (1962)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"72_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-642-40273-9_3","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"TM Chan","year":"2013","unstructured":"Chan, T.M.: Quake heaps: a simple alternative to fibonacci heaps. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol. 8066, pp. 27\u201332. Springer, Heidelberg (2013)"},{"issue":"11","key":"72_CR3","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1145\/50087.50096","volume":"31","author":"JR Driscoll","year":"1988","unstructured":"Driscoll, J.R., Gabow, H.N., Shrairman, R., Tarjan, R.E.: Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Commun. ACM 31(11), 1343\u20131354 (1988)","journal-title":"Commun. ACM"},{"key":"72_CR4","doi-asserted-by":"crossref","unstructured":"Elmasry, A.: Pairing heaps with o(log log n) decrease cost. In: Claire Mathieu, editor, SODA, pp. 471\u2013476. SIAM (2009)","DOI":"10.1137\/1.9781611973068.52"},{"issue":"4","key":"72_CR5","first-page":"493","volume":"2","author":"A Elmasry","year":"2010","unstructured":"Elmasry, A.: The violation heap: a relaxed Fibonacci-like heap. Discrete Math., Alg. and Appl. 2(4), 493\u2013504 (2010)","journal-title":"Discrete Math., Alg. and Appl."},{"key":"72_CR6","volume-title":"Handbook of data structures and applications","author":"ML Fredman","year":"2005","unstructured":"Fredman, M.L.: Binomial, Fibonacci, and pairing heaps. In: Mehta, D.P., Sahni, S. (eds.) Handbook of data structures and applications. Chapman & Hall\/CRC, Boca Raton (2005)"},{"issue":"1","key":"72_CR7","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01840439","volume":"1","author":"ML Fredman","year":"1986","unstructured":"Fredman, M.L., Sedgewick, R., Sleator, D.D., Tarjan, R.E.: The pairing heap: A new form of self-adjusting heap. Algorithmica 1(1), 111\u2013129 (1986)","journal-title":"Algorithmica"},{"issue":"3","key":"72_CR8","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"72_CR9","first-page":"8","volume":"1978","author":"LJ Guibas","year":"1978","unstructured":"Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. FOCS 1978, 8\u201321 (1978)","journal-title":"FOCS"},{"key":"72_CR10","doi-asserted-by":"crossref","unstructured":"H\u00f8yer, P.: A general technique for implementation of efficient priority queues. In: ISTCS 1995, ISTCS 1995, p. 57-, Washington, DC, IEEE Computer Society (1995)","DOI":"10.1109\/ISTCS.1995.377045"},{"issue":"6","key":"72_CR11","doi-asserted-by":"publisher","first-page":"1463","DOI":"10.1137\/100785351","volume":"40","author":"B Haeupler","year":"2011","unstructured":"Haeupler, B., Sen, S., Tarjan, R.E.: Rank-pairing heaps. SIAM J. Comput. 40(6), 1463\u20131485 (2011)","journal-title":"SIAM J. Comput."},{"key":"72_CR12","unstructured":"Karger, D.: untitled manuscript. unpublished (2000)"},{"key":"72_CR13","unstructured":"Karger, D.: personal communication (2013)"},{"issue":"1","key":"72_CR14","doi-asserted-by":"publisher","first-page":"3:1","DOI":"10.1145\/1328911.1328914","volume":"4","author":"H Kaplan","year":"2008","unstructured":"Kaplan, H., Tarjan, R.E.: Thin heaps, thick heaps. ACM Trans. Algorithms 4(1), 3:1\u20133:14 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"72_CR15","unstructured":"Kaplan, H., Tarjan, R.E., Zwick, U.: Fibonacci heaps revisited (2014). CoRR, abs\/1407.5750"},{"key":"72_CR16","doi-asserted-by":"crossref","unstructured":"Li, J., Peebles, J.: Replacing mark bits with randomness in fibonacci heaps (2014). CoRR, abs\/1407.2569","DOI":"10.1007\/978-3-662-47672-7_72"},{"key":"72_CR17","unstructured":"Peterson, G.: A balanced tree scheme for meldable heaps with updates. Technical Report GIT-ICS-87-23, Georgia Institute of Technology (1987)"},{"key":"72_CR18","first-page":"174","volume":"2005","author":"S Pettie","year":"2005","unstructured":"Pettie, S.: Towards a final analysis of pairing heaps. FOCS 2005, 174\u2013183 (2005)","journal-title":"FOCS"},{"key":"72_CR19","unstructured":"Price, E.: Randomized Fibonacci heaps. unpublished (2009)"},{"issue":"1","key":"72_CR20","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0166-218X(02)00219-6","volume":"126","author":"T Takaoka","year":"2003","unstructured":"Takaoka, T.: Theory of 2\u20133 heaps. Discrete Appl. Math. 126(1), 115\u2013128 (2003)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_72","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:09:59Z","timestamp":1748459399000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_72"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_72","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}