Skip to main content
Springer Nature Link
Log in

Improved Upper Bounds for Pairing Heaps

  • Conference paper
  • First Online:
Algorithm Theory - SWAT 2000 (SWAT 2000)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1851))

Included in the following conference series:

Abstract

Pairing heaps are shown to have constant amortized time insert and zero amortized time meld, thus improving the previous O(log n) amortized time bound on these operations. It is also shown that pairing heaps have a distribution sensitive behavior whereby the cost to perform an extract-min on an element x is O(log min(n, k)) where k is the number of heap operations performed since x’s insertion. Fredman has observed that pairing heaps can be used to merge sorted lists of varying sized optimally, within constant factors. Utilizing the distribution sensitive behavior of pairing heap, an alternative method the employs pairing heaps for optimal list merging is derived.

Research supported by NSF grant CCR-9732689.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Chapter
USD 29.95
Price excludes VAT (Canada)
eBook
USD 84.99
Price excludes VAT (Canada)
Softcover Book
USD 109.99
Price excludes VAT (Canada)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. R. Cole. On the dynamic finger conjecture for splay trees. part ii: The proof. Technical Report Computer Science TR1995-701, New York Univerity, 1995.

    Google Scholar 

  2. R. Cole, B. Mishra, J. Schmidt, and A. Siegel. On the dynamic finger conjecture for splay trees. part i: Splay sorting log n-block sequences. Technical Report Computer Science TR1995-700, New York Univerity, 1995.

    Google Scholar 

  3. M. L. Fredman. Manuscript in preparation.

    Google Scholar 

  4. M. L Fredman. On the efficiency of pairing heaps and related data structures. JACM, 46(4):473–501, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  5. M. L Fredman. A priority queue transform. In Workshop on Algorithm Engineering, pages 243–257, 1999. LNCS 1668.

    Chapter  Google Scholar 

  6. M. L. Fredman, R. Sedgewick, D. D. Sleator, and R. E. Tarjan. The pairing heap: A new form of self-adjusting heap. Algorithmica, 1:111–129, 1986.

    Article  MATH  MathSciNet  Google Scholar 

  7. M. L Fredman and R. E. Tarjan. Fibonacci heaps and their used in improved network optimization algorithms. JACM, 34:596–615, 1987.

    Article  MathSciNet  Google Scholar 

  8. Haim Kaplan and Robert E. Tarjan. New heap data structures. Technical Report Computer Science TR-597-99, Princeton University, 1999.

    Google Scholar 

  9. D. D. Sleator and R. E. Tarjan. Self-adjusting binary trees. JACM, 32:652–686, 1985.

    Article  MATH  MathSciNet  Google Scholar 

  10. D. D. Sleator and R. E. Tarjan. Self-adjusting heaps. SIAM Journal of Computing, 15:52–69, 1986.

    Article  MATH  MathSciNet  Google Scholar 

  11. J. T. Stasko and J. S. Vitter. Pairing heaps: experiments and analysis. CACM, 15:234–249, 1987.

    MathSciNet  Google Scholar 

  12. R. Sundar. Amoritzed Complexity of Data Structures. PhD thesis, New York University, 1991.

    Google Scholar 

  13. R. E. Tarjan. Sequential access in splay trees takes linear time. Combinatorica, 5:367–378, 1985.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Rutgers University, New Brunswick, NJ, 08903

    John Iacono

Authors
  1. John Iacono
    View author publications

    Search author on:PubMed Google Scholar

Rights and permissions

Reprints and permissions

Copyright information

© 2000 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Iacono, J. (2000). Improved Upper Bounds for Pairing Heaps. In: Algorithm Theory - SWAT 2000. SWAT 2000. Lecture Notes in Computer Science, vol 1851. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44985-X_5

Download citation

  • DOI: https://doi.org/10.1007/3-540-44985-X_5

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-67690-4

  • Online ISBN: 978-3-540-44985-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics