Skip to main content

Analysis of Smooth Heaps and Slim Heaps

Author(s): Hartmann, Maria; Kozma, László; Sinnamon, Corwin; Tarjan, Robert E

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr16688j6s
Full metadata record
DC FieldValueLanguage
dc.contributor.authorHartmann, Maria-
dc.contributor.authorKozma, László-
dc.contributor.authorSinnamon, Corwin-
dc.contributor.authorTarjan, Robert E-
dc.date.accessioned2023-12-23T22:22:48Z-
dc.date.available2023-12-23T22:22:48Z-
dc.date.issued2021en_US
dc.identifier.citationHartmann, Maria, László Kozma, Corwin Sinnamon, and Robert E. Tarjan. "Analysis of Smooth Heaps and Slim Heaps." In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 198 (2021): pp. 79:1-79:20. doi:10.4230/LIPIcs.ICALP.2021.79en_US
dc.identifier.issn1868-8969-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr16688j6s-
dc.description.abstractThe smooth heap is a recently introduced self-adjusting heap [Kozma, Saranurak, 2018] similar to the pairing heap [Fredman, Sedgewick, Sleator, Tarjan, 1986]. The smooth heap was obtained as a heap-counterpart of Greedy BST, a binary search tree updating strategy conjectured to be instance-optimal [Lucas, 1988], [Munro, 2000]. Several adaptive properties of smooth heaps follow from this connection; moreover, the smooth heap itself has been conjectured to be instance-optimal within a certain class of heaps. Nevertheless, no general analysis of smooth heaps has existed until now, the only previous analysis showing that, when used in sorting mode (n insertions followed by n delete-min operations), smooth heaps sort n numbers in O(nlg n) time. In this paper we describe a simpler variant of the smooth heap we call the slim heap. We give a new, self-contained analysis of smooth heaps and slim heaps in unrestricted operation, obtaining amortized bounds that match the best bounds known for self-adjusting heaps. Previous experimental work has found the pairing heap to dominate other data structures in this class in various settings. Our tests show that smooth heaps and slim heaps are competitive with pairing heaps, outperforming them in some cases, while being comparably easy to implement.en_US
dc.format.extent79:1 - 79:20en_US
dc.language.isoen_USen_US
dc.relation.ispartof48th International Colloquium on Automata, Languages, and Programmingen_US
dc.relation.ispartofseriesLeibniz International Proceedings in Informatics (LIPIcs);-
dc.rightsFinal published version. This is an open access article.en_US
dc.titleAnalysis of Smooth Heaps and Slim Heapsen_US
dc.typeConference Articleen_US
dc.identifier.doi10.4230/LIPIcs.ICALP.2021.79-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
SmoothHeapsSlim.pdf1.36 MBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.