Improved Bounds for Multipass Pairing Heaps and Path-Balanced Binary Search Trees

Authors Dani Dorfman, Haim Kaplan, László Kozma, Seth Pettie, Uri Zwick



PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.24.pdf
  • Filesize: 0.59 MB
  • 13 pages

Document Identifiers

Author Details

Dani Dorfman
  • Blavatnik School of Computer Science, Tel Aviv University, Israel
Haim Kaplan
  • Blavatnik School of Computer Science, Tel Aviv University, Israel
László Kozma
  • Eindhoven University of Technology, The Netherlands
Seth Pettie
  • University of Michigan
Uri Zwick
  • Blavatnik School of Computer Science, Tel Aviv University, Israel

Cite AsGet BibTex

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 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.24

Abstract

We revisit multipass pairing heaps and path-balanced binary search trees (BSTs), two classical algorithms for data structure maintenance. The pairing heap is a simple and efficient "self-adjusting" heap, introduced in 1986 by Fredman, Sedgewick, Sleator, and Tarjan. In the multipass variant (one of the original pairing heap variants described by Fredman et al.) the minimum item is extracted via repeated pairing rounds in which neighboring siblings are linked. Path-balanced BSTs, proposed by Sleator (cf. Subramanian, 1996), are a natural alternative to Splay trees (Sleator and Tarjan, 1983). In a path-balanced BST, whenever an item is accessed, the search path leading to that item is re-arranged into a balanced tree. Despite their simplicity, both algorithms turned out to be difficult to analyse. Fredman et al. showed that operations in multipass pairing heaps take amortized O(log n * log log n / log log log n) time. For searching in path-balanced BSTs, Balasubramanian and Raman showed in 1995 the same amortized time bound of O(log n * log log n / log log log n), using a different argument. In this paper we show an explicit connection between the two algorithms and improve both bounds to O(log n * 2^{log^* n} * log^* n), respectively O(log n * 2^{log^* n} * (log^* n)^2), where log^* denotes the slowly growing iterated logarithm function. These are the first improvements in more than three, resp. two decades, approaching the information-theoretic lower bound of Omega(log n).

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • data structure
  • priority queue
  • pairing heap
  • binary search tree

Metrics

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

References

  1. R. Balasubramanian and Venkatesh Raman. Path balance heuristic for self-adjusting binary search trees. In Proceedings of FSTTCS, pages 338-348, 1995. URL: http://dx.doi.org/10.1007/3-540-60692-0_59.
  2. Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Self-adjusting binary search trees: What makes them tick? In ESA 2015, pages 300-312, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_26.
  3. Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. The landscape of bounds for binary search trees. CoRR, abs/1603.04892, 2016. URL: http://arxiv.org/abs/1603.04892.
  4. Michael L. Fredman. On the efficiency of pairing heaps and related data structures. J. ACM, 46(4):473-501, 1999. URL: http://dx.doi.org/10.1145/320211.320214.
  5. 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: http://dx.doi.org/10.1007/BF01840439.
  6. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. In 25th Annual Symposium on Foundations of Computer Science, West Palm Beach, Florida, USA, 24-26 October 1984, pages 338-346, 1984. URL: http://dx.doi.org/10.1109/SFCS.1984.715934.
  7. George F. Georgakopoulos and David J. McClurkin. Generalized template splay: A basic theory and calculus. Comput. J., 47(1):10-19, 2004. URL: http://dx.doi.org/10.1093/comjnl/47.1.10.
  8. John Iacono. Improved upper bounds for pairing heaps. In Algorithm Theory - SWAT 2000, 7th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 5-7, 2000, Proceedings, pages 32-45, 2000. URL: http://dx.doi.org/10.1007/3-540-44985-X_5.
  9. John Iacono. In pursuit of the dynamic optimality conjecture. In Space-Efficient Data Structures, Streams, and Algorithms, volume 8066 of Lecture Notes in Computer Science, pages 236-250. Springer Berlin Heidelberg, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40273-9_16.
  10. Donald E. Knuth. The Art of Computer Programming, Volume 1 (3rd Ed.): Fundamental Algorithms. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1997. Google Scholar
  11. Donald E. Knuth. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998. Google Scholar
  12. Daniel H. Larkin, Siddhartha Sen, and Robert Endre Tarjan. A back-to-basics empirical study of priority queues. In 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2014, Portland, Oregon, USA, January 5, 2014, pages 61-72, 2014. URL: http://dx.doi.org/10.1137/1.9781611973198.7.
  13. Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, volume 1 of EATCS Monographs on Theoretical Computer Science. Springer, 1984. URL: http://dx.doi.org/10.1007/978-3-642-69672-5.
  14. Bernard M. E. Moret and Henry D. Shapiro. An empirical analysis of algorithms for constructing a minimum spanning tree, pages 400-411. Springer Berlin Heidelberg, Berlin, Heidelberg, 1991. URL: http://dx.doi.org/10.1007/BFb0028279.
  15. 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, 2005. URL: http://dx.doi.org/10.1109/SFCS.2005.75.
  16. Daniel D. Sleator, William P. Thurston, and Robert Endre Tarjan. Rotation distance,triangulations,and hyperbolic geometry. Technical Report CS-TR-131-88, Princeton University (NJ US), 1988. URL: http://opac.inria.fr/record=b1019357.
  17. Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. J. ACM, 32(3):652-686, 1985. URL: http://dx.doi.org/10.1145/3828.3835.
  18. John T. Stasko and Jeffrey Scott Vitter. Pairing heaps: Experiments and analysis. Commun. ACM, 30(3):234-249, 1987. URL: http://dx.doi.org/10.1145/214748.214759.
  19. Ashok Subramanian. An explanation of splaying. J. Algorithms, 20(3):512-525, 1996. URL: http://dx.doi.org/10.1006/jagm.1996.0025.
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