{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T23:54:38Z","timestamp":1778025278259,"version":"3.51.4"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1986,11,1]],"date-time":"1986-11-01T00:00:00Z","timestamp":531187200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1986,11]]},"DOI":"10.1007\/bf01840439","type":"journal-article","created":{"date-parts":[[2005,7,13]],"date-time":"2005-07-13T21:29:13Z","timestamp":1121290153000},"page":"111-129","source":"Crossref","is-referenced-by-count":155,"title":["The pairing heap: A new form of self-adjusting heap"],"prefix":"10.1007","volume":"1","author":[{"given":"Michael L.","family":"Fredman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Sedgewick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel D.","family":"Sleator","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01840439_CR1","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0207026","volume":"7","author":"M. R. Brown","year":"1978","unstructured":"M. R. Brown, \u201cImplementation and analysis of binomial queue algorithms,\u201dSIAM J. Comput. 7 (1978), 298\u2013319.","journal-title":"SIAM J. Comput."},{"key":"BF01840439_CR2","series-title":"Technical Report STAN-CS-72-259","volume-title":"Linear lists and priority queues as balanced binary trees","author":"C. A. Crane","year":"1972","unstructured":"C. A. Crane, \u201cLinear lists and priority queues as balanced binary trees,\u201d Technical Report STAN-CS-72-259, Computer Science Department, Stanford University, Stanford, CA, 1972."},{"key":"BF01840439_CR3","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/355588.365103","volume":"7","author":"R. W. Floyd","year":"1964","unstructured":"R. W. Floyd, \u201cAlgorithm 245: Treesort 3,\u201dComm. ACM 7 (1964), 701.","journal-title":"Comm. ACM"},{"key":"BF01840439_CR4","doi-asserted-by":"crossref","unstructured":"M. L. Fredman and R. E. Tarjan, \u201cFibonacci heaps and their uses in improved network optimization algorithms,\u201dJ. Assoc. Comput. Mach., submitted; alsoProc. 25th Annual IEEE Symp. on Found. of Comput. Sci. (1984), 338\u2013346.","DOI":"10.1109\/SFCS.1984.715934"},{"key":"BF01840439_CR5","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, Z. Galil, and T. Spencer, \u201cEfficient implementation of graph algorithms using contraction,\u201dProc. 25th Annual IEEE Symp. on Found. of Comput. Sci. (1984).","DOI":"10.1109\/SFCS.1984.715935"},{"key":"BF01840439_CR6","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, \u201cEfficient algorithms for finding minimum spanning trees in undirected and directed graphs,\u201dCombinatorica, to appear.","DOI":"10.1007\/BF02579168"},{"key":"BF01840439_CR7","unstructured":"D. W. Jones, \u201cAn empirical comparison of priority queues and event set algorithms,\u201dComm. ACM, submitted."},{"key":"BF01840439_CR8","volume-title":"The Art of Computer Programming, Vol. 1: Fundamental Algorithms","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth,The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Second Edition, Addison-Wesley, Reading, MA, 1973.","edition":"Second Edition"},{"key":"BF01840439_CR9","volume-title":"The Art of Computer Programming, Vol. 3:Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth,The Art of Computer Programming, Vol. 3:Sorting and Searching, Addison-Wesley, Reading, MA, 1973."},{"key":"BF01840439_CR10","doi-asserted-by":"crossref","unstructured":"D. D. Sleator and R. E. Tarjan, \u201cSelf-adjusting binary trees, Proc. 15th AnnualACM Symp. on Theory of Comput. (1983), 235\u2013245.","DOI":"10.1145\/800061.808752"},{"key":"BF01840439_CR11","doi-asserted-by":"crossref","unstructured":"D. D. Sleator and R. E. Tarjan, \u201cSelf-adjusting heaps,\u201dSIAM J. Comput., to appear.","DOI":"10.1137\/0215004"},{"key":"BF01840439_CR12","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. D. Sleator","year":"1985","unstructured":"D. D. Sleator and R. E. Tarjan, \u201cSelf-adjusting binary search trees,\u201dJ. Assoc. Comput. Mach. 32 (1985), 652\u2013686.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01840439_CR13","doi-asserted-by":"crossref","unstructured":"R. E. Tarjan,Data Structures and Network Algorithms, CBMS 44, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.","DOI":"10.1137\/1.9781611970265"},{"key":"BF01840439_CR14","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan, \u201cAmortized computational complexity,\u201dSIAM J. Alg. Disc. Meth. 6 (1985), 306\u2013318.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"BF01840439_CR15","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1145\/359460.359478","volume":"21","author":"J. Vuillemin","year":"1978","unstructured":"J. Vuillemin, \u201cA data structure for manipulating priority queues,\u201dComm. ACM 21 (1978), 309\u2013314.","journal-title":"Comm. ACM"},{"key":"BF01840439_CR16","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J. W. J. Williams","year":"1964","unstructured":"J. W. J. Williams, \u201cAlgorithm 232: Heapsort,\u201dComm. ACM 7 (1964), 347\u2013348.","journal-title":"Comm. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840439.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01840439\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840439","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,13]],"date-time":"2021-07-13T14:07:18Z","timestamp":1626185238000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01840439"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,11]]},"references-count":16,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1986,11]]}},"alternative-id":["BF01840439"],"URL":"https:\/\/doi.org\/10.1007\/bf01840439","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,11]]}}}