{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T18:05:50Z","timestamp":1783965950840,"version":"3.55.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T00:00:00Z","timestamp":1736121600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Independent Research Fund Denmark","award":["9131-00113B"],"award-info":[{"award-number":["9131-00113B"]}]},{"DOI":"10.13039\/501100001732","name":"Danish National Research Foundation","doi-asserted-by":"crossref","award":["DNRF84"],"award-info":[{"award-number":["DNRF84"]}],"id":[{"id":"10.13039\/501100001732","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100007277","name":"Center for Massive Data Algorithmics","doi-asserted-by":"crossref","award":["CCF-0830676"],"award-info":[{"award-number":["CCF-0830676"]}],"id":[{"id":"10.13039\/501100007277","id-type":"DOI","asserted-by":"crossref"}]},{"name":"US-Israel Binational Science Foundation","award":["2006204"],"award-info":[{"award-number":["2006204"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,4,30]]},"abstract":"<jats:p>\n                    We present the\n                    <jats:italic toggle=\"yes\">strict Fibonacci heap<\/jats:italic>\n                    , the first pointer-based heap implementation with time bounds matching those of Fibonacci heaps in the worst case. Strict Fibonacci heaps support make-heap, insert, find-min, meld and decrease-key in worst-case\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(1)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    time, and delete and delete-min in worst-case\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(\\lg n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    time, where\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(n\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    is the size of the heap. The data structure uses linear space.\n                  <\/jats:p>\n                  <jats:p>A previous solution achieving the same time bounds in the RAM model made essential use of arrays and extensive use of redundant counter schemes to maintain balance. Our solution uses neither. Our key simplification is to discard the structure of the smaller heap when doing a meld, and to use the pigeonhole principle in place of the redundant counter mechanism to maintain balance.<\/jats:p>","DOI":"10.1145\/3707692","type":"journal-article","created":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T05:15:12Z","timestamp":1733807712000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Strict Fibonacci Heaps"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9054-915X","authenticated-orcid":false,"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[{"name":"Department of Computer Science, Aarhus University, Aarhus, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8040-4125","authenticated-orcid":false,"given":"George","family":"Lagogiannis","sequence":"additional","affiliation":[{"name":"Agricultural University of Athens, Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7505-5768","authenticated-orcid":false,"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Princeton University, Princeton, NJ, USA, and Intertrust Technologies, Sunnyvale, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,1,6]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60220-8_70"},{"key":"e_1_3_2_3_2","first-page":"52","volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Brodal Gerth St\u00f8lting","year":"1996","unstructured":"Gerth St\u00f8lting Brodal. 1996. Worst-case efficient priority queues. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 52\u201358. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=313852.313883"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","unstructured":"Gerth St\u00f8lting Brodal. 2013. A survey on priority queues. In Proceedings of the International Conference on Space-Efficient Data Structures Streams and Algorithms: Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Lecture Notes in Computer Science Vol. 8066 Springer 150\u2013163. DOI: 10.1007\/978-3-642-40273-9_11","DOI":"10.1007\/978-3-642-40273-9_11"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214082"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-19487-8_1"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40273-9_3"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/906397"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2018.24"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2018.13"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/50087.50096"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_19"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.03.002"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.52"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830910000838"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3147138"},{"key":"e_1_3_2_17_2","series-title":"CRPIT","first-page":"45","volume-title":"Proceedings of the 13th Computing: The Australasian Theory Symposium","volume":"65","author":"Elmasry Amr","year":"2007","unstructured":"Amr Elmasry, Claus Jensen, and Jyrki Katajainen. 2007. On the power of structural violations in priority queues. In Proceedings of the 13th Computing: The Australasian Theory Symposium. CRPIT, Vol. 65, Australian Computer Society, 45\u201353. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=1273694.1273700"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-008-0070-7"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320214"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840439"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/100785351"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3093240"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.79"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1995.377045"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509990"},{"key":"e_1_3_2_27_2","volume-title":"New Heap Data Structures","author":"Kaplan Haim","year":"1999","unstructured":"Haim Kaplan and Robert E. Tarjan. 1999. New Heap Data Structures. Technical Report TR-597-99. Department of Computer Science, Princeton University. Retrieved from https:\/\/www.cs.princeton.edu\/research\/techreps\/TR-597-99"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328914"},{"key":"e_1_3_2_29_2","volume-title":"The Art of Computer Programming, Volume I: Fundamental Algorithms","author":"Knuth Donald E.","year":"1973","unstructured":"Donald E. Knuth. 1973. The Art of Computer Programming, Volume I: Fundamental Algorithms (2nd ed.). Addison-Wesley.","edition":"2"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1195188"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_72"},{"key":"e_1_3_2_32_2","volume-title":"A Balanced Tree Scheme for Meldable Heaps With Updates","author":"Peterson Gary L.","year":"1987","unstructured":"Gary L. Peterson. 1987. A Balanced Tree Scheme for Meldable Heaps With Updates. Technical Report GIT-ICS-87-23. School of Information and Computer Science, Georgia Institute of Technology."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.75"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch23"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch24"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3708989"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215004"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/359460.359478"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/512274.512284"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3707692","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3707692","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T17:32:17Z","timestamp":1783963937000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3707692"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,6]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1145\/3707692"],"URL":"https:\/\/doi.org\/10.1145\/3707692","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,6]]},"assertion":[{"value":"2019-04-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-26","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}