We describe a heap data structure that supports Minimum, Insert, and Borrow at worst-case cost, Delete at worst-case cost including at most element comparisons, and Union at worst-case cost including at most element comparisons, where 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.
Accepté le :
DOI : 10.1051/ita/2017010
Mots-clés : Data structures, heaps, numeral systems, comparison complexity
@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
, 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
, , and , Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Commun. ACM 31 (1988) 1343–1354. | DOI | MR
, Weak-heap sort. BIT 33 (1993) 372–381. | DOI | MR | Zbl
, and , The weak-heap data structure: Variants and applications. J. Discrete Algorithms 16 (2012) 187–205. | DOI | MR | Zbl
, and , Multipartite priority queues. ACM Trans. Algorithms 5 (2008) Article 14. | DOI | MR | Zbl
, and , Two new methods for constructing double-ended priority queues from priority queues. Comput. 83 (2008) 193–204. | DOI | MR | Zbl
, and , 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
and , 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
, A data structure for manipulating priority queues. Commun. ACM 21 (1978) 309–315. | DOI | MR | Zbl
Cité par Sources :
