nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

A Linear Potential Function for Pairing Heaps

verfasst von : John Iacono, Mark Yagnatinsky

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel On the Parameterized Parallel Complexity and the Vertex Cover Problem

Nächstes Kapitel 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

Titel: A Linear Potential Function for Pairing Heaps
verfasst von: John Iacono
Mark Yagnatinsky
Verlag: Springer International Publishing
Buch: Combinatorial Optimization and Applications
Print ISBN: 978-3-319-48748-9

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"