Quake heaps: A simple alternative to Fibonacci heaps

Timothy M. Chan

doi:10.1007/978-3-642-40273-9_3

Quake heaps: A simple alternative to Fibonacci heaps

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

Abstract

This note describes a data structure that has the same theoretical performance as Fibonacci heaps, supporting decrease-key operations in O (1) amortized time and delete-min operations in O (log n) amortized time. The data structure is simple to explain and analyze, and may be of pedagogical value.

Original language	English (US)
Title of host publication	Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday
Publisher	Springer
Pages	27-32
Number of pages	6
ISBN (Print)	9783642402722
DOIs	https://doi.org/10.1007/978-3-642-40273-9_3
State	Published - 2013
Externally published	Yes
Event	Conference on Space-Efficient Data Structures, Streams, and Algorithms - Waterloo, ON, Canada Duration: Aug 15 2013 → Aug 16 2013

Publication series

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

Other

Other	Conference on Space-Efficient Data Structures, Streams, and Algorithms
Country/Territory	Canada
City	Waterloo, ON
Period	8/15/13 → 8/16/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-642-40273-9_3

Library availability

Discover UIUC Full Text

Cite this

Chan, T. M. (2013). Quake heaps: A simple alternative to Fibonacci heaps. In Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday (pp. 27-32). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8066 LNCS). Springer. https://doi.org/10.1007/978-3-642-40273-9_3

Quake heaps: A simple alternative to Fibonacci heaps. / Chan, Timothy M.
Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Springer, 2013. p. 27-32 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8066 LNCS).

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

Chan, TM 2013, Quake heaps: A simple alternative to Fibonacci heaps. in Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8066 LNCS, Springer, pp. 27-32, Conference on Space-Efficient Data Structures, Streams, and Algorithms, Waterloo, ON, Canada, 8/15/13. https://doi.org/10.1007/978-3-642-40273-9_3

Chan TM. Quake heaps: A simple alternative to Fibonacci heaps. In Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Springer. 2013. p. 27-32. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-40273-9_3

@inproceedings{46ec973f560a4d5f8f7c43cf5337762a,

title = "Quake heaps: A simple alternative to Fibonacci heaps",

abstract = "This note describes a data structure that has the same theoretical performance as Fibonacci heaps, supporting decrease-key operations in O (1) amortized time and delete-min operations in O (log n) amortized time. The data structure is simple to explain and analyze, and may be of pedagogical value.",

author = "Chan, {Timothy M.}",

year = "2013",

doi = "10.1007/978-3-642-40273-9_3",

language = "English (US)",

isbn = "9783642402722",

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

publisher = "Springer",

pages = "27--32",

booktitle = "Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday",

address = "Germany",

note = "Conference on Space-Efficient Data Structures, Streams, and Algorithms ; Conference date: 15-08-2013 Through 16-08-2013",

}

TY - GEN

T1 - Quake heaps

T2 - Conference on Space-Efficient Data Structures, Streams, and Algorithms

AU - Chan, Timothy M.

PY - 2013

Y1 - 2013

N2 - This note describes a data structure that has the same theoretical performance as Fibonacci heaps, supporting decrease-key operations in O (1) amortized time and delete-min operations in O (log n) amortized time. The data structure is simple to explain and analyze, and may be of pedagogical value.

AB - This note describes a data structure that has the same theoretical performance as Fibonacci heaps, supporting decrease-key operations in O (1) amortized time and delete-min operations in O (log n) amortized time. The data structure is simple to explain and analyze, and may be of pedagogical value.

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

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

U2 - 10.1007/978-3-642-40273-9_3

DO - 10.1007/978-3-642-40273-9_3

M3 - Conference contribution

AN - SCOPUS:84894140024

SN - 9783642402722

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

SP - 27

EP - 32

BT - Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday

PB - Springer

Y2 - 15 August 2013 through 16 August 2013

ER -

Quake heaps: A simple alternative to Fibonacci heaps

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this