Bipartite binomial heaps

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Bipartite binomial heaps. / Elmasry, Amr; Jensen, Claus; Katajainen, Jyrki.

In: RAIRO - Theoretical Informatics and Applications, Vol. 51, No. 3, 07.2017, p. 121-133.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Elmasry, A, Jensen, C & Katajainen, J 2017, 'Bipartite binomial heaps', RAIRO - Theoretical Informatics and Applications, vol. 51, no. 3, pp. 121-133. https://doi.org/10.1051/ita/2017010

APA

Elmasry, A., Jensen, C., & Katajainen, J. (2017). Bipartite binomial heaps. RAIRO - Theoretical Informatics and Applications, 51(3), 121-133. https://doi.org/10.1051/ita/2017010

Vancouver

Elmasry A, Jensen C, Katajainen J. Bipartite binomial heaps. RAIRO - Theoretical Informatics and Applications. 2017 Jul;51(3):121-133. https://doi.org/10.1051/ita/2017010

Author

Elmasry, Amr ; Jensen, Claus ; Katajainen, Jyrki. / Bipartite binomial heaps. In: RAIRO - Theoretical Informatics and Applications. 2017 ; Vol. 51, No. 3. pp. 121-133.

Bibtex

@article{39eecad19d484e8981d83d74e3af33fd,
title = "Bipartite binomial heaps",
abstract = "We describe a heap data structure that supports Minimum, Insert, and Borrow at O(1) worst-case cost, Delete at O(lgn) worst-case cost including at most lgn + O(1) element comparisons, and Union at O(lgn) worst-case cost including at most lgn + O(lglgn) element comparisons, where n denotes the (total) number of elements stored in the data structure(s) prior to the operation. As the resulting data structure consists of two components that are different variants of binomial heaps, we call it a bipartite binomial heap. Compared to its counterpart, a multipartite binomial heap, the new structure is simpler and mergeable, still retaining the efficiency of the other operations.",
keywords = "Comparison complexity, Data structures, Heaps, Numeral systems",
author = "Amr Elmasry and Claus Jensen and Jyrki Katajainen",
year = "2017",
month = jul,
doi = "10.1051/ita/2017010",
language = "English",
volume = "51",
pages = "121--133",
journal = "RAIRO - Theoretical Informatics and Applications",
issn = "0988-3754",
publisher = "E D P Sciences",
number = "3",

}

RIS

TY - JOUR

T1 - Bipartite binomial heaps

AU - Elmasry, Amr

AU - Jensen, Claus

AU - Katajainen, Jyrki

PY - 2017/7

Y1 - 2017/7

N2 - We describe a heap data structure that supports Minimum, Insert, and Borrow at O(1) worst-case cost, Delete at O(lgn) worst-case cost including at most lgn + O(1) element comparisons, and Union at O(lgn) worst-case cost including at most lgn + O(lglgn) element comparisons, where n denotes the (total) number of elements stored in the data structure(s) prior to the operation. As the resulting data structure consists of two components that are different variants of binomial heaps, we call it a bipartite binomial heap. Compared to its counterpart, a multipartite binomial heap, the new structure is simpler and mergeable, still retaining the efficiency of the other operations.

AB - We describe a heap data structure that supports Minimum, Insert, and Borrow at O(1) worst-case cost, Delete at O(lgn) worst-case cost including at most lgn + O(1) element comparisons, and Union at O(lgn) worst-case cost including at most lgn + O(lglgn) element comparisons, where n denotes the (total) number of elements stored in the data structure(s) prior to the operation. As the resulting data structure consists of two components that are different variants of binomial heaps, we call it a bipartite binomial heap. Compared to its counterpart, a multipartite binomial heap, the new structure is simpler and mergeable, still retaining the efficiency of the other operations.

KW - Comparison complexity

KW - Data structures

KW - Heaps

KW - Numeral systems

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

U2 - 10.1051/ita/2017010

DO - 10.1051/ita/2017010

M3 - Journal article

AN - SCOPUS:85038628824

VL - 51

SP - 121

EP - 133

JO - RAIRO - Theoretical Informatics and Applications

JF - RAIRO - Theoretical Informatics and Applications

SN - 0988-3754

IS - 3

ER -

ID: 188448401