Bipartite binomial heaps
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 3, pp. 121-133.

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
Mots clés : 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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ita/2017010/

G.S. Brodal, Fast meldable priority queues. Proc. of the 4th International Workshop on Algorithms and Data Structures. In vol. 955 of Lect. Notes Comput. Sci. Springer, Berlin/Heidelberg (1995) 282–290. | MR

M.R. Brown, Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7 (1978) 298–319. | DOI | MR | Zbl

M.J. Clancy and D.E. Knuth, A programming and problem-solving seminar. Technical report, STAN-CS-77-606. Dept. Comput. Sci., Stanford Univ., Stanford (1977).

T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 3rd Edition. The MIT Press, Cambridge (2009). | MR

J.R. Driscoll, H.N. Gabow, R. Shrairman and R.E. Tarjan, Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Commun. ACM 31 (1988) 1343–1354. | DOI | MR

R.D. Dutton, Weak-heap sort. BIT 33 (1993) 372–381. | DOI | MR | Zbl

S. Edelkamp, A. Elmasry and J. Katajainen, The weak-heap data structure: Variants and applications. J. Discrete Algorithms 16 (2012) 187–205. | DOI | MR | Zbl

A. Elmasry, C. Jensen and J. Katajainen, Multipartite priority queues. ACM Trans. Algorithms 5 (2008) Article 14. | DOI | MR | Zbl

A. Elmasry, C. Jensen and J. Katajainen, Two new methods for constructing double-ended priority queues from priority queues. Comput. 83 (2008) 193–204. | DOI | MR | Zbl

A. Elmasry, C. Jensen and J. Katajainen, Two-tier relaxed heaps. Acta Inform. 45 (2008) 193–210. | DOI | MR | Zbl

A. Elmasry, C. Jensen and J. Katajainen, Strictly-regular number system and data structures, Proc. of the 12th Scandinavian Symposium and Workshops on Algorithm Theory. In vol. 6139 of Lect. Notes Comput. Sci. Springer, Berlin/Heidelberg (2010) 26–37. | MR | Zbl

A. Elmasry and J. Katajainen, Worst-case optimal priority queues via extended regular counters. Proc. of the 7th International Computer Science Symposium in Russia. In vol. 7353 of Lect. Notes in Comput. Sci. Springer, Berlin/Heidelberg (2012) 130–142. | MR | Zbl

A. Elmasry and J. Katajainen, Fat heaps without regular counters. Discrete Math. Algorithms Appl. 5 (2013) Article 1360006. | DOI | MR | Zbl

T. Hagerup, Sorting and searching on the word RAM, Proc. of the 15th Annual Symposium on Theoretical Aspects of Computer Science. In vol. 1373 of Lect. Notes in Comput. Sci. Springer, Berlin/Heidelberg (1998) 366–398. | MR

H. Kaplan, N. Shafrir and R.E. Tarjan, Meldable heaps and Boolean union-find, Proc. of the 34th Annual ACM Symposium on Theory of Computing. ACM (2002) 573–582. | MR | Zbl

C. Okasaki, Purely Functional Data Structures. Cambridge University Press, Cambridge (1998). | Zbl

J. Vuillemin, A data structure for manipulating priority queues. Commun. ACM 21 (1978) 309–315. | DOI | MR | Zbl

Cité par Sources :