Overview of binomial pyramids based on different number systems

Vasiliy K. Gulakov, Konstantin V. Gulakov

Abstract


The article provides an overview of binomial data structures based on various number systems. This approach improves the performance of operations on binomial pyramids, such as increasing and decreasing the number of elements, inserting elements, merging pyramids. Various number systems are considered: binary, redundant, nonzero, regular, oblique, and their combinations. The structure of binomial pyramids is well described by a binary number equal to the number of elements in the pyramid. By working with these numbers, you can efficiently perform various operations on pyramidal structures. The problem with representing a binary number is that increasing or decreasing the number by one can cause many of the digits of the number to cascade, which affects the result in the worst case. In order to get away from this situation, other number systems are used. The article briefly discusses various number systems, their combinations and their capabilities.

Full Text:

PDF (Russian)

References


Gulakov V. K., Gulakov K. V. Monopiramidal'nye struktury dannyh. – M.: Gorjachaja linija –Telekom, 2019. –148 s.: il.

Brodal, G. Fast Meldable Priority Queues. WADS 1995: 282-290

Brodal, G. S. Worst-case efficient priority queues, Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM/SIAM (1996), 52-58.

Brodal, G. S. Okasaki, C. Optimal purely functional priority queues, Journal of Functional Programming 6, 6 (1996), 839-857.

Carlsson, S. Munro, J. I. Poblete, P. V. An implicit binomial queue with constant insertion time, Proceedings of the 1st Scandinavian Workshop on Algorithm Theory,Lecture Notes in Computer Science 318, Springer-Verlag (1988), 1-13.

Clancy, M. J. A programming and problem-solving seminar / M. J. Clancy, D. E. Knuth // Technical Report STAN-CS-77-606, Department of Computer Science, Stanford University, APRIL 1977

Elmasry, A.. On the power of structural violations in priority queues. / A. Elmasry, C. Jensen, J. Katajainen. // In Proc. 13th Computing: The Australasian Theory Symposium., volume 65 of CRPIT, pages 45–53. Australian Computer Society, 2007.

Elmasry, A. The Magic of a Number System / Amr Elmasry, Claus Jensen, and Jyrki Katajainen from book Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings (pp.156-165)

Elmasry, A. Strictly-regular number system and data structures / A. Elmasry, C. Jensen, J. Katajainen // 12th Scandinavian Symposium and Workshops on Algorithm Theory (2010), Bergen, Norway, LNCS 6139, 26–37.

Elmasry, A. Two skew-binary numeral systems and one application/ Amr Elmasry, Claus Jensen, Jyrki Katajainen // Published in Theory of Computing Systems 2011

Elmasry, A., Jensen, C., Katajainen, J.: Two-tier relaxed heaps. Acta Informatica 45(3), 193–210 (2008)

Elmasry, A. Katajainen, J. Worst-case optimal priority queues via extended regular counters, 7th International Computer Science Symposium in Russia (2012), Nizhny Novgorod, Russia, LNCS 7353, 130–142.

Elmasry, A. Improving the efficiency of priority-queue structures / Amr Elmasry, Claus Jensen, Jyrki Katajainen // University of Copenhagen, Denmark, 23 October 2012

Elmasry and J. Katajainen, In-place binary counters, 38th Inter-national Symposium on Mathematical Foundations of Computer Science (2013), Klosterneuburg, Austria, LNCS 8087, 349–360

Elmasry, A. Number Systems and Data Structures, Alexandria University https://ru.scribd.com/document/175364781/Numeral-Systems-and-Data-Structures

Guibas, L. J. Edward M. McCreight, Michael F. Plass, Janet R. Roberts: A New Representation for Linear Lists. STOC 1977: 49-60

Haim Kaplan, Robert Endre Tarjan: Persistent lists with catenation via recursive slow-down. STOC 1995: 93-102

Kaplan, H., Tarjan, R.E.: Purely functional representations of catenable sorted lists. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 202–211. ACM, New York (1996)

Kaplan, H. Nira Shafrir, Robert Endre Tarjan: Meldable heaps and boolean union-find. STOC 2002: 573-582

Eugene W. Myers. An applicative random-access stack. Information Processing Letters, 17(5):241–248, December 1983. (pp. 76, 82, 84)

Okasaki, C. Purely Functional Data Structures /Dissertation for the degree of Doctor of Philosophy. CMU-CS-96-177, September 1996

Vuillemin J. A unifying look at data structures // Communications of the ACM. 1980. 23. P. 229–239.


Refbacks

  • There are currently no refbacks.


Abava  Absolutech Convergent 2020

ISSN: 2307-8162