Geodesic
Bipartite binomial heaps
Elmasry, Amr1 ; Jensen, Claus2  ; Katajainen, Jyrki3  
1 Department of Computer Engineering and Systems, Alexandria University, Egypt
2 The Royal Library, Copenhagen, Denmark
3 Department of Computer Science, University of Copenhagen, Denmark
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 3, pp. 121-133

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2017010
Classification : 68P05, 68W01, 68W40
Keywords: Data structures, heaps, numeral systems, comparison complexity

Elmasry, Amr 1 ; Jensen, Claus 2 ; Katajainen, Jyrki 3

1 Department of Computer Engineering and Systems, Alexandria University, Egypt
2 The Royal Library, Copenhagen, Denmark
3 Department of Computer Science, University of Copenhagen, Denmark 
@article{ITA_2017__51_3_121_0,
     author = {Elmasry, Amr and Jensen, Claus and Katajainen, Jyrki},
     title = {Bipartite binomial heaps},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {121--133},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {3},
     year = {2017},
     doi = {10.1051/ita/2017010},
     zbl = {1390.68209},
     mrnumber = {3743413},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2017010/}
}
TY  - JOUR
AU  - Elmasry, Amr
AU  - Jensen, Claus
AU  - Katajainen, Jyrki
TI  - Bipartite binomial heaps
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2017
SP  - 121
EP  - 133
VL  - 51
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2017010/
DO  - 10.1051/ita/2017010
LA  - en
ID  - ITA_2017__51_3_121_0
ER  - 
%0 Journal Article
%A Elmasry, Amr
%A Jensen, Claus
%A Katajainen, Jyrki
%T Bipartite binomial heaps
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2017
%P 121-133
%V 51
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2017010/
%R 10.1051/ita/2017010
%G en
%F ITA_2017__51_3_121_0
Elmasry, Amr; Jensen, Claus; Katajainen, Jyrki. Bipartite binomial heaps. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 3, pp. 121-133. doi: 10.1051/ita/2017010

Cité par Sources :