TY - GEN
T1 - Analysis of smooth heaps and slim heaps
AU - Hartmann, Maria
AU - Kozma, László
AU - Sinnamon, Corwin
AU - Tarjan, Robert E.
N1 - Publisher Copyright:
© 2021 Maria Hartmann, László Kozma, Corwin Sinnamon, and Robert E. Tarjan.
PY - 2021/7/1
Y1 - 2021/7/1
N2 - The 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(n lg 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.
AB - The 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(n lg 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.
KW - Amortized analysis
KW - Data structure
KW - Heap
KW - Priority queue
KW - Self-adjusting
UR - http://www.scopus.com/inward/record.url?scp=85115294926&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115294926&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2021.79
DO - 10.4230/LIPIcs.ICALP.2021.79
M3 - Conference contribution
AN - SCOPUS:85115294926
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
A2 - Bansal, Nikhil
A2 - Merelli, Emanuela
A2 - Worrell, James
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
Y2 - 12 July 2021 through 16 July 2021
ER -