Hollow heaps

Thomas Dueholm; Haim Kaplan; Robert E. Tarjan; Uri Zwick

doi:10.1007/978-3-662-47672-7_56

Hollow heaps

Thomas Dueholm, Haim Kaplan, Robert E. Tarjan, Uri Zwick

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

2 Scopus citations

Abstract

We introduce the hollow heap, a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete-min take O(1) time, worst case as well as amortized; delete and delete-min take O(log n) amortized time. Hollow heaps are by far the simplest structure to achieve this. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease-key operations, and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. Lazy deletion produces hollow nodes (nodes without items), giving the data structure its name.

Original language	English (US)
Title of host publication	Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
Editors	Magnus M. Halldorsson, Naoki Kobayashi, Bettina Speckmann, Kazuo Iwama
Publisher	Springer Verlag
Pages	689-700
Number of pages	12
ISBN (Print)	9783662476710
DOIs	https://doi.org/10.1007/978-3-662-47672-7_56
State	Published - 2015
Event	42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 - Kyoto, Japan Duration: Jul 6 2015 → Jul 10 2015

Publication series

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

Other

Other	42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
Country/Territory	Japan
City	Kyoto
Period	7/6/15 → 7/10/15

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-662-47672-7_56

Cite this

Dueholm, T., Kaplan, H., Tarjan, R. E., & Zwick, U. (2015). Hollow heaps. In M. M. Halldorsson, N. Kobayashi, B. Speckmann, & K. Iwama (Eds.), Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings (pp. 689-700). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9134). Springer Verlag. https://doi.org/10.1007/978-3-662-47672-7_56

Dueholm, Thomas ; Kaplan, Haim ; Tarjan, Robert E. et al. / Hollow heaps. Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. editor / Magnus M. Halldorsson ; Naoki Kobayashi ; Bettina Speckmann ; Kazuo Iwama. Springer Verlag, 2015. pp. 689-700 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4844436c153145a1b2e53c19a322d59a,

title = "Hollow heaps",

abstract = "We introduce the hollow heap, a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete-min take O(1) time, worst case as well as amortized; delete and delete-min take O(log n) amortized time. Hollow heaps are by far the simplest structure to achieve this. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease-key operations, and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. Lazy deletion produces hollow nodes (nodes without items), giving the data structure its name.",

author = "Thomas Dueholm and Haim Kaplan and Tarjan, {Robert E.} and Uri Zwick",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015.; 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 ; Conference date: 06-07-2015 Through 10-07-2015",

year = "2015",

doi = "10.1007/978-3-662-47672-7_56",

language = "English (US)",

isbn = "9783662476710",

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

publisher = "Springer Verlag",

pages = "689--700",

editor = "Halldorsson, {Magnus M.} and Naoki Kobayashi and Bettina Speckmann and Kazuo Iwama",

booktitle = "Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings",

address = "Germany",

}

Dueholm, T, Kaplan, H, Tarjan, RE & Zwick, U 2015, Hollow heaps. in MM Halldorsson, N Kobayashi, B Speckmann & K Iwama (eds), Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9134, Springer Verlag, pp. 689-700, 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015, Kyoto, Japan, 7/6/15. https://doi.org/10.1007/978-3-662-47672-7_56

Hollow heaps. / Dueholm, Thomas; Kaplan, Haim; Tarjan, Robert E. et al.
Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. ed. / Magnus M. Halldorsson; Naoki Kobayashi; Bettina Speckmann; Kazuo Iwama. Springer Verlag, 2015. p. 689-700 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9134).

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

TY - GEN

T1 - Hollow heaps

AU - Dueholm, Thomas

AU - Kaplan, Haim

AU - Tarjan, Robert E.

AU - Zwick, Uri

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

PY - 2015

Y1 - 2015

N2 - We introduce the hollow heap, a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete-min take O(1) time, worst case as well as amortized; delete and delete-min take O(log n) amortized time. Hollow heaps are by far the simplest structure to achieve this. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease-key operations, and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. Lazy deletion produces hollow nodes (nodes without items), giving the data structure its name.

AB - We introduce the hollow heap, a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete-min take O(1) time, worst case as well as amortized; delete and delete-min take O(log n) amortized time. Hollow heaps are by far the simplest structure to achieve this. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease-key operations, and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. Lazy deletion produces hollow nodes (nodes without items), giving the data structure its name.

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

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

U2 - 10.1007/978-3-662-47672-7_56

DO - 10.1007/978-3-662-47672-7_56

M3 - Conference contribution

AN - SCOPUS:84950158459

SN - 9783662476710

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

SP - 689

EP - 700

BT - Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings

A2 - Halldorsson, Magnus M.

A2 - Kobayashi, Naoki

A2 - Speckmann, Bettina

A2 - Iwama, Kazuo

PB - Springer Verlag

T2 - 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015

Y2 - 6 July 2015 through 10 July 2015

ER -

Dueholm T, Kaplan H, Tarjan RE, Zwick U. Hollow heaps. In Halldorsson MM, Kobayashi N, Speckmann B, Iwama K, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. Springer Verlag. 2015. p. 689-700. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-47672-7_56

Hollow heaps

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this