{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:29Z","timestamp":1787340389506,"version":"build-2736575974"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>We introduce the rank-pairing heap, an implementation of heaps that combines the asymptotic efficiency of Fibonacci heaps with much of the simplicity of pairing heaps. Other heap implementations that match the bounds of Fibonacci heaps do so by maintaining a balance condition on the trees representing the heap. In contrast to these structures but like pairing heaps, our trees can evolve to have arbitrary (unbalanced) structure. Also like pairing heaps, our structure requires at most one cut and no other restructuring per key decrease, in the worst case: the only changes that can cascade during a key decrease are changes in node ranks. Although our data structure is simple, its analysis is not.<\/jats:p>","DOI":"10.1137\/100785351","type":"journal-article","created":{"date-parts":[[2011,11,16]],"date-time":"2011-11-16T10:43:49Z","timestamp":1321440229000},"page":"1463-1485","source":"Crossref","is-referenced-by-count":14,"title":["Rank-Pairing Heaps"],"prefix":"10.1137","volume":"40","author":[{"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Siddhartha","family":"Sen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,11,15]]},"reference":[{"key":"R1","first-page":"1259","volume":"3","author":"Adel'son-Vel'skii G. M.","year":"1962","journal-title":"Sov. Math. Dokl.","ISSN":"https:\/\/id.crossref.org\/issn\/0197-6788","issn-type":"print"},{"key":"R2","unstructured":"G. S. Brodal,\n                      Worst-case efficient priority queues\n                      , in Proceedings of the Seventh ACM-SIAM Symposium on Discrete Algorithms (SODA), 1996, pp. 52\u201358."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1017\/S095679680000201X"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0207026"},{"key":"R5","unstructured":"T. M. Chan,\n                      Quake Heaps: A Simple Alternative to Fibonacci Heaps\n                      , 2009; available online at http:\/\/www.cs.uwaterloo.ca\/$\\!_{^{\\sim}}\\!$tmchan\/heap.ps."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/50087.50096"},{"key":"R8","unstructured":"R. D. Dutton,\n                      The Weak-Heap Data Structure\n                      , Technical report CS-TR-92-09, University of Central Florida, Orlando, FL, 1992."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.032"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"A. Elmasry,\n                      Pairing heaps with $\\mathrm{O}(\\log\\log n)$ decrease cost\n                      , in Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009, pp. 471\u2013476.","DOI":"10.1137\/1.9781611973068.52"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"A. Elmasry,\n                      The violation heap: A relaxed Fibonacci-like heap\n                      , in Proceedings of the 16th International Conference on Computing and Combinatorics (COCOON), 2010, pp. 479\u2013488.","DOI":"10.1007\/978-3-642-14031-0_51"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-008-0070-7"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320214"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840439"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80064-9"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579168"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"L. J. Guibas and R. Sedgewick,\n                      A dichromatic framework for balanced trees\n                      , in Proceedings of the 19th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1978, pp. 8\u201321.","DOI":"10.1109\/SFCS.1978.3"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"B. Haeupler, S. Sen, and R. E. Tarjan,\n                      Rank-pairing heaps\n                      , in Proceedings of the 17th European Symposium on Algorithms (ESA), 2009, pp. 659\u2013670.","DOI":"10.1007\/978-3-642-04128-0_59"},{"key":"R20","unstructured":"Y. Han and M. Thorup,\n                      Integer sorting in $\\mathrm{O}(n   \\sqrt{\\log \\log n})$ expected time and linear space\n                      , in Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS), 2002, pp. 135\u2013144."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"P. H\u00f8yer,\n                      A general technique for implementation of efficient priority queues\n                      , in Proceedings of the Third Israeli Symposium on the Theory of Computing and Systems (ISTCS), 1995, pp. 57\u201366.","DOI":"10.1109\/ISTCS.1995.377045"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"H. Kaplan, N. Shafrir, and R. E. Tarjan,\n                      Meldable heaps and boolean union-find\n                      , in Proceedings of the 34th ACM Symposium on Theory of Computing (STOC), 2002, pp. 573\u2013582.","DOI":"10.1145\/509907.509990"},{"key":"R23","unstructured":"H. Kaplan and R. E. Tarjan,\n                      New Heap Data Structures\n                      , Technical report TR-597-99, Department of Computer Science, Princeton University, Princeton, NJ, 1999."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328914"},{"key":"R25","unstructured":"D. E. Knuth,\n                      The Art of Computer Programming, Volume\n                      1:\n                      Fundamental Algorithms\n                      , Addison-Wesley, Upper Saddle River, NJ, 1973."},{"key":"R26","unstructured":"D. E. Knuth,\n                      The Art of Computer Programming, Volume\n                      3:\n                      Sorting and Searching\n                      , Addison-Wesley, Reading, MA, 1973."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758771"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"B. M. E. Moret and H. D. Shapiro,\n                      An empirical analysis of algorithms for constructing a minimum spanning tree\n                      , in Proceedings of the 2nd Workshop on Algorithms and Data Structures (WADS), 1991, pp. 400\u2013411.","DOI":"10.1007\/BFb0028279"},{"key":"R29","unstructured":"G. L. Peterson,\n                      A Balanced Tree Scheme for Meldable Heaps with Updates\n                      , Technical report GIT-ICS-87-23, School of Informatics and Computer Science, Georgia Institute of Technology, Atlanta, GA, 1987."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"S. Pettie,\n                      Towards a final analysis of pairing heaps\n                      , in Proceedings of 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2005, pp. 174\u2013183.","DOI":"10.1109\/SFCS.2005.75"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1145\/214748.214759"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"T. Takaoka,\n                      Theory of trinomial heaps\n                      , in Proceedings of the Sixth International Conference on Computing and Combinatorics (COCOON), 2000, pp. 362\u2013372.","DOI":"10.1007\/3-540-44968-X_36"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00219-6"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/0606031"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.003"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"M. Thorup,\n                      Equivalence between priority queues and sorting\n                      , J. ACM, 54 (2007), 28.","DOI":"10.1145\/1314690.1314692"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1145\/359460.359478"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100785351","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:32:50Z","timestamp":1787337170000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100785351"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100785351"],"URL":"https:\/\/doi.org\/10.1137\/100785351","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}