Improved upper bounds for pairing heaps

John Iacono

doi:10.1007/3-540-44985-X

Improved upper bounds for pairing heaps

John Iacono

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Pairing heaps are shown to have constant amortized time in-sert 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 per-form 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 sensi-tive behavior of pairing heap, an alternative method the employs pairing heaps for optimal list merging is derived.

Original language	English (US)
Title of host publication	Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings
Editors	Magnús M. Halldórsson
Publisher	Springer Verlag
Pages	32-45
Number of pages	14
ISBN (Print)	3540676902, 9783540676904
DOIs	https://doi.org/10.1007/3-540-44985-X
State	Published - 2000
Event	7th Scandinavian Workshop on Algorithm Theory, SWAT 2000 - Bergen, Norway Duration: Jul 5 2000 → Jul 7 2000

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1851
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	7th Scandinavian Workshop on Algorithm Theory, SWAT 2000
Country/Territory	Norway
City	Bergen
Period	7/5/00 → 7/7/00

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-44985-X

Cite this

Iacono, J. (2000). Improved upper bounds for pairing heaps. In M. M. Halldórsson (Ed.), Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings (pp. 32-45). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1851). Springer Verlag. https://doi.org/10.1007/3-540-44985-X

Improved upper bounds for pairing heaps. / Iacono, John.
Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings. ed. / Magnús M. Halldórsson. Springer Verlag, 2000. p. 32-45 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1851).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Iacono, J 2000, Improved upper bounds for pairing heaps. in MM Halldórsson (ed.), Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1851, Springer Verlag, pp. 32-45, 7th Scandinavian Workshop on Algorithm Theory, SWAT 2000, Bergen, Norway, 7/5/00. https://doi.org/10.1007/3-540-44985-X

Iacono J. Improved upper bounds for pairing heaps. In Halldórsson MM, editor, Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings. Springer Verlag. 2000. p. 32-45. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44985-X

@inproceedings{ff05196cf3f44dc2bf77b3f05a06f2d4,

title = "Improved upper bounds for pairing heaps",

abstract = "Pairing heaps are shown to have constant amortized time in-sert 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 per-form 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 sensi-tive behavior of pairing heap, an alternative method the employs pairing heaps for optimal list merging is derived.",

author = "John Iacono",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2000.; 7th Scandinavian Workshop on Algorithm Theory, SWAT 2000 ; Conference date: 05-07-2000 Through 07-07-2000",

year = "2000",

doi = "10.1007/3-540-44985-X",

language = "English (US)",

isbn = "3540676902",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "32--45",

editor = "Halld{\'o}rsson, {Magn{\'u}s M.}",

booktitle = "Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings",

}

TY - GEN

T1 - Improved upper bounds for pairing heaps

AU - Iacono, John

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2000.

PY - 2000

Y1 - 2000

N2 - Pairing heaps are shown to have constant amortized time in-sert 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 per-form 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 sensi-tive behavior of pairing heap, an alternative method the employs pairing heaps for optimal list merging is derived.

AB - Pairing heaps are shown to have constant amortized time in-sert 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 per-form 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 sensi-tive behavior of pairing heap, an alternative method the employs pairing heaps for optimal list merging is derived.

UR - http://www.scopus.com/inward/record.url?scp=84956859079&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84956859079&partnerID=8YFLogxK

U2 - 10.1007/3-540-44985-X

DO - 10.1007/3-540-44985-X

M3 - Conference contribution

AN - SCOPUS:84956859079

SN - 3540676902

SN - 9783540676904

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 32

EP - 45

BT - Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings

A2 - Halldórsson, Magnús M.

PB - Springer Verlag

T2 - 7th Scandinavian Workshop on Algorithm Theory, SWAT 2000

Y2 - 5 July 2000 through 7 July 2000

ER -

Improved upper bounds for pairing heaps

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this