Document Open Access Logo

Analysis of Smooth Heaps and Slim Heaps

Authors Maria Hartmann, László Kozma, Corwin Sinnamon , Robert E. Tarjan

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.79.pdf
  • Filesize: 1.32 MB
  • 20 pages

Document Identifiers

Author Details

Maria Hartmann
  • Institut für Informatik, Freie Universität Berlin, Germany
László Kozma
  • Institut für Informatik, Freie Universität Berlin, Germany
Corwin Sinnamon
  • Department of Computer Science, Princeton University, NJ, USA
Robert E. Tarjan
  • Department of Computer Science, Princeton University, NJ, USA
  • Intertrust Technologies, Sunnyvale, CA, USA

Funding

  • Hartmann, Maria: Work supported by DFG grant KO 6140/1-1.
  • Kozma, László: Work supported by DFG grant KO 6140/1-1.
  • Tarjan, Robert E.: Research at Princeton University partially supported by an innovation research grant from Princeton and a gift from Microsoft.

Cite AsGet BibTex

Maria Hartmann, 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 79:1-79:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.79

Abstract

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(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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • data structure
  • heap
  • priority queue
  • amortized analysis
  • self-adjusting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Prosenjit Bose, Jonathan F. Buss, and Anna Lubiw. Pattern matching for permutations. Inf. Process. Lett., 65(5):277-283, 1998. URL: https://doi.org/10.1016/S0020-0190(97)00209-3.
  2. Gerth Stølting Brodal. A survey on priority queues. In Andrej Brodnik, Alejandro López-Ortiz, Venkatesh Raman, and Alfredo Viola, editors, Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, volume 8066 of Lecture Notes in Computer Science, pages 150-163. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40273-9_11.
  3. Gerth Stølting Brodal, George Lagogiannis, and Robert E Tarjan. Strict fibonacci heaps. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1177-1184, 2012. Google Scholar
  4. Erik D. Demaine, Dion Harmon, John Iacono, Daniel M. Kane, and Mihai Pǎtraşcu. The geometry of binary search trees. In SODA 2009, pages 496-505, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496825.
  5. Dani Dorfman, Haim Kaplan, László Kozma, Seth Pettie, and Uri Zwick. Improved bounds for multipass pairing heaps and path-balanced binary search trees. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 of LIPIcs, pages 24:1-24:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.24.
  6. Amr Elmasry. Toward optimal self-adjusting heaps. ACM Trans. Algorithms, 13(4):55:1-55:14, 2017. URL: https://doi.org/10.1145/3147138.
  7. Amr Elmasry, Arash Farzan, and John Iacono. A priority queue with the time-finger property. Journal of Discrete Algorithms, 16:206-212, 2012. Google Scholar
  8. Michael L. Fredman. On the efficiency of pairing heaps and related data structures. J. ACM, 46(4):473-501, 1999. URL: https://doi.org/10.1145/320211.320214.
  9. Michael L. Fredman, Robert Sedgewick, Daniel Dominic Sleator, and Robert Endre Tarjan. The pairing heap: A new form of self-adjusting heap. Algorithmica, 1(1):111-129, 1986. URL: https://doi.org/10.1007/BF01840439.
  10. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596-615, 1987. URL: https://doi.org/10.1145/28869.28874.
  11. Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan, and Uri Zwick. Hollow heaps. ACM Trans. Algorithms, 13(3):42:1-42:27, 2017. URL: https://doi.org/10.1145/3093240.
  12. Maria Hartmann. Efficiency of self-adjusting heap variants. Master’s thesis, Freie Universität Berlin, 2020. URL: http://www.mi.fu-berlin.de/inf/groups/ag-ti/theses/master_finished/hartmann_maria/index.html.
  13. John Iacono. Improved upper bounds for pairing heaps. In Magnús M. Halldórsson, editor, Algorithm Theory - SWAT 2000, 7th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 5-7, 2000, Proceedings, volume 1851 of Lecture Notes in Computer Science, pages 32-45. Springer, 2000. URL: https://doi.org/10.1007/3-540-44985-X_5.
  14. John Iacono and Özgür Özkan. Why some heaps support constant-amortized-time decrease-key operations, and others do not. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 637-649, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_53.
  15. John Iacono and Thatchaphol Saranurak. personal communication. Google Scholar
  16. László Kozma and Thatchaphol Saranurak. Smooth heaps and a dual view of self-adjusting data structures. SIAM J. Comput., 49(5), 2020. URL: https://doi.org/10.1137/18M1195188.
  17. Daniel H. Larkin, Siddhartha Sen, and Robert Endre Tarjan. A back-to-basics empirical study of priority queues. In Catherine C. McGeoch and Ulrich Meyer, editors, 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2014, Portland, Oregon, USA, January 5, 2014, pages 61-72. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973198.7.
  18. Caleb C. Levy and Robert E. Tarjan. A new path from splay to dynamic optimality. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1311-1330. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.80.
  19. Joan M. Lucas. Canonical forms for competitive binary search tree algorithms. Tech. Rep. DCS-TR-250, Rutgers University, 1988. Google Scholar
  20. J.Ian Munro. On the competitiveness of linear search. In Mike S. Paterson, editor, Algorithms - ESA 2000, volume 1879 of Lecture Notes in Computer Science, pages 338-345. Springer Berlin Heidelberg, 2000. URL: https://doi.org/10.1007/3-540-45253-2_31.
  21. Seth Pettie. Towards a final analysis of pairing heaps. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 174-183. IEEE Computer Society, 2005. URL: https://doi.org/10.1109/SFCS.2005.75.
  22. Peter Sanders. Fast priority queues for cached memory. ACM J. Exp. Algorithmics, 5:7, 2000. URL: https://doi.org/10.1145/351827.384249.
  23. Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, and Roman Dementiev. Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-25209-0.
  24. Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652-686, 1985. Google Scholar
  25. John T. Stasko and Jeffrey Scott Vitter. Pairing heaps: Experiments and analysis. Commun. ACM, 30(3):234-249, 1987. URL: https://doi.org/10.1145/214748.214759.
  26. Robert Endre Tarjan. Amortized computational complexity. SIAM Journal on Algebraic Discrete Methods, 6(2):306-318, 1985. Google Scholar
  27. John William Joseph Williams. Algorithm 232: heapsort. Commun. ACM, 7:347-348, 1964. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact