Top

Published in:

2016 | OriginalPaper | Chapter

A Linear Potential Function for Pairing Heaps

Authors : John Iacono, Mark Yagnatinsky

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present the first potential function for pairing heaps with linear range. This implies that the runtime of a short sequence of operations is faster than previously known. It is also simpler than the only other potential function known to give constant amortized time for insertion.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter On the Parameterized Parallel Complexity and the Vertex Cover Problem

next chapter Amortized Efficiency of Ranking and Unranking Left-Child Sequences in Lexicographic Order

[Col00]

Cole, R.: On the dynamic finger conjecture for splay trees. Part II: the proof. SIAM J. Comput. 30(1), 44–85 (2000)MathSciNetCrossRefMATH

[Elm09a]

Elmasry, A.: Pairing heaps with \(O(\log \log n)\) decrease cost. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 471–476, January 2009

[Elm09b]

Elmasry, A.: Pairing heaps with costless meld, April 2009. http://arxiv.org/abs/0903.4130. In: Part I of the Proceedings of the 18th Annual European Symposium Algorithms, ESA, pp. 183–193, September 2010

[Fre99]

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

[FSST86]

Fredman, M.L., Sedgewick, R., Sleator, D.D., Tarjan, R.E.: The pairing heap: a new form of self-adjusting heap. Algorithmica 1(1), 111–129 (1986)MathSciNetCrossRefMATH

[FT84]

Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. In: Proceedings of the 25th IEEE Symposium on the Foundations of Computer Science, FOCS, pp. 338–346, October 1984. J. ACM 34(3), 596–615 (1987)

[HST09]

Haeupler, B., Sen, S., Tarjan, R.E.: Rank-pairing heaps. In: Proceedings of the 17th Annual European Symposium on Algorithms, ESA, pp. 659–670, September 2009. SIAM J. Comput. 40(6), pp. 1463–1485 (2011)

[Iac00]

Iacono, J.: Improved upper bounds for pairing heaps. In: Halldórsson, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 32–45. Springer, Heidelberg (2000). arXiv.org/abs/1110.4428 (2011)CrossRef

[IY16]

Iacono, J., Yagnatinsky, M.: A Linear Potential Function for Pairing Heaps. arXiv.org/abs/1606.06389 (2016)

[IO14]

Why some heaps support constant-amortized-time decrease-key operations, others do not. First version: Iacono, J.: arXiv.org/abs/1302.6641, February 2013. Later: Iacono, J., Özkan, Ö.: 41st International Colloquium on Automata, Languages, and Programming, ICALP, pp. 637–649, July 2014

[LST14]

Larkin, D.H., Sen, S., Tarjan, R.E.: A back-to-basics empirical study of priority queues. In: 2014 Proceedings of the 16th Workshop on Algorithm Engineering, Experiments, ALENEX, pp. 61–72, January 2014. arXiv.org/abs/1403.0252, March 2014

[Pet05]

Pettie, S.: Towards a final analysis of pairing heaps. In: 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 174–183, October 2005

[ST85]

Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652–686 (1985)MathSciNetCrossRefMATH

[SV86]

Stasko, J.T., Vitter, J.S.: Pairing heaps: experiments and analysis. Commun. ACM 30(3), 234–249 (1987)MathSciNetCrossRef

[Vui78]

Vuillemin, J.: A data structure for manipulating priority queues. Commun. ACM 21(4), 309–315 (1978)MathSciNetCrossRefMATH

[Yag16]

Yagnatinsky, M.: Thinnest V-shapes, biggest angles, and lowest potentials. Ph.D. thesis, NYU Tandon School of Engineering, May 2016. http://cse.poly.edu/~myag/thesis.pdf

Title: A Linear Potential Function for Pairing Heaps
Authors: John Iacono
Mark Yagnatinsky
Publisher: Springer International Publishing
Book: Combinatorial Optimization and Applications
Print ISBN: 978-3-319-48748-9

Electronic ISBN: 978-3-319-48749-6

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-48749-6_36

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner