{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T06:38:57Z","timestamp":1784011137854,"version":"3.55.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"Microsoft"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,10,31]]},"abstract":"<jats:p>\n            Since the invention of the pairing heap by Fredman, Sedgewick, Sleator, and Tarjan [\n            <jats:xref ref-type=\"bibr\">8<\/jats:xref>\n            ], it has been an open question whether this or any other simple \u201cself-adjusting\u201d heap supports decrease-key operations in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathrm{O}(\\log\\log 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 number of heap items. Using powerful new techniques, we answer this question in the affirmative. We prove that both slim and smooth heaps, recently introduced self-adjusting heaps, support heap operations in the following amortized time bounds:\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathrm{O}(\\log n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            for delete-min and delete,\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathrm{O}(\\log\\log n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            for decrease-key, and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathrm{O}(1)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            for all other heap operations, including insert and meld, 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 number of heap items that are eventually deleted: Items inserted but never deleted do not count in the bounds. We also analyze the multipass pairing heap, a variant of pairing heaps. For this heap implementation, we obtain the same bounds except for decrease-key, for which our bound is\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathrm{O}(\\log\\log n\\cdot\\log\\log\\log n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , where again items that are never deleted do not count in\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            . Our bounds significantly improve the best previously known bounds for all three data structures. For slim and smooth heaps our bounds are tight, since they match lower bounds of Iacono and \u00d6zkan [\n            <jats:xref ref-type=\"bibr\">13<\/jats:xref>\n            ].\n          <\/jats:p>","DOI":"10.1145\/3708989","type":"journal-article","created":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T10:34:11Z","timestamp":1734950051000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficiency of Self-Adjusting Heaps"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0280-9498","authenticated-orcid":false,"given":"Corwin","family":"Sinnamon","sequence":"first","affiliation":[{"name":"Department of Computer Science, Princeton University, Princeton, NJ, United States"}],"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, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40273-9_11"},{"key":"e_1_3_2_3_2","first-page":"496","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201909)","author":"Demaine Erik D.","year":"2009","unstructured":"Erik D. Demaine, Dion Harmon, John Iacono, Daniel M. Kane, and Mihai P\u01cetra\u015fcu. 2009. The geometry of binary search trees. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201909), 496\u2013505. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=1496770.1496825"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2018.24"},{"key":"e_1_3_2_5_2","first-page":"471","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Elmasry Amr","year":"2009","unstructured":"Amr Elmasry. 2009. Pairing heaps with \\(o(\\log\\log n)\\) decrease cost. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 471\u2013476."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3147138"},{"key":"e_1_3_2_7_2","first-page":"411","volume-title":"Proceedings of the Workshop on Algorithms and Data Structures","author":"Fox Kyle","year":"2011","unstructured":"Kyle Fox. 2011. Upper bounds for maximally greedy binary search trees. In Proceedings of the Workshop on Algorithms and Data Structures. Springer, 411\u2013422."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320214"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840439"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3093240"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.79"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44985-X_5"},{"key":"e_1_3_2_14_2","unstructured":"John Iacono and \u00d6zg\u00fcr \u00d6zkan. 2014. A tight lower bound for decrease-key in the pure heap model. arXiv:1407.6665. Retrieved from https:\/\/arxiv.org\/abs\/1407.6665"},{"key":"e_1_3_2_15_2","unstructured":"Haim Kaplan Robert Endre Tarjan and Uri Zwick. 2014. Fibonacci heaps revisited. arXiv:1407.5750 Retrieved from http:\/\/arxiv.org\/abs\/1407.5750"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1195188"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973198.7"},{"key":"e_1_3_2_18_2","volume-title":"Canonical Forms for Competitive Binary Search Tree Algorithms","author":"Lucas Joan M.","year":"1988","unstructured":"Joan M. Lucas. 1988. Canonical Forms for Competitive Binary Search Tree Algorithms. Tech. Rep. DCS-TR-250, Rutgers University."},{"key":"e_1_3_2_19_2","first-page":"152","volume-title":"Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS \u201915)","volume":"9214","author":"Mehlhorn Kurt","year":"2015","unstructured":"Kurt Mehlhorn and Thatchaphol Saranurak. 2015. Greedy is an almost optimal deque. In Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS \u201915). Vol. 9214, Springer, 152."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45253-2_31"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.75"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/AAI29392569"},{"key":"e_1_3_2_23_2","unstructured":"Corwin Sinnamon and Robert Tarjan. 2022. A simpler proof that pairing heaps take \\(o(1)\\) amortized time per insertion. arXiv:2208.11791. Retrieved from https:\/\/arxiv.org\/abs\/2208.11791"},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1137\/1.9781611977554.ch23","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Sinnamon Corwin","year":"2023","unstructured":"Corwin Sinnamon and Robert E. Tarjan. 2023. A nearly-tight analysis of multipass pairing heaps. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 535\u2013548."},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1137\/1.9781611977554.ch24","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Sinnamon Corwin","year":"2023","unstructured":"Corwin Sinnamon and Robert E. Tarjan. 2023. A tight analysis of Slim heaps and smooth heaps. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 549\u2013567."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/3485"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3708989","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T05:40:33Z","timestamp":1757396433000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708989"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,8]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1145\/3708989"],"URL":"https:\/\/doi.org\/10.1145\/3708989","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,8]]},"assertion":[{"value":"2023-07-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-23","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}