Weak heap
Abstract
the article is devoted to one variety of pyramidal data structures - a weak pyramid. Some problems where weak pyramids are more effective are considered. A brief comparison of it and its species with the most popular pyramid structure shows the ability to perform basic operations on the data with minimum complexity. The article gives detailed description of the weak pyramid structure in the array form and in the coherent structure form. Preference is given to the connected structure visibility. Examples of performing various operations on the structure under consideration are given with the help of figures, and an assessment of its implementation complexity is given. To increase the efficiency of insertion operations, the approach using buffers is considered. The connection between a weak pyramid and a binomial pyramid is considered. Here the concept of an ideal weak pyramid is used. The article outlines the ways of experimental research of a weak pyramid in various situations and practical problems.
Full Text:
PDF (Russian)References
Gulakov, V.K. Drozhashhaja piramida / V.K. Gulakov, K.V. Gulakov. International Journal of Open Information Technologies ISSN: 2307-8162 vol. 6, no.1, 2018
Bruun, A., Edelkamp, S., Katajainen, J., Rasmussen, J. Policy-based benchmarking of weak heaps and their relatives, in: Proceedings of the 9th International Symposium on Experimental Algorithms, vol. 6049 of Lecture Notes in Computer Science, Springer-Verlag, 424-435, 2010.
Dutton, R. D. Weak-heap sort, BIT 33 (3) (1993) 372-381.
Edelkamp, S., Elmasry, A., Katajainen, J. The weak-heap data structure: Variants and applications, Journal of Discrete Algorithms 16 (2012) 187-205.
Edelkamp, S., Elmasry, A., Katajainen, J. A catalogue of weak-heap programs, CPH STL Report 2012-2, Department of Computer Science, University of Copenhagen, 2012.
Edelkamp S., Elmasry A., Katajainen J.i. Weak Heaps Engineered 23rd International Workshop on Combinatorial Algorithms held in Tamil Nadu, India, in July 2012.
Edelkamp, S. Rank-relaxed weak queues: Faster than pairing and Fibonacci heaps., Technical Report 54, TZI, Universit¨at Bremen, 2009.
Edelkamp, S., Elmasry A., Katajainen, J. The Weak-Heap Family of Priority Queues in Theory and Praxis Proceedings of the Eighteenth Computing: The Australasian Theory Symposium (CATS 2012), Melbourne, Australia, 2012.
Elmasry, A. Violation heaps: A better substitute for fibonacci heaps. CoRR, abs/0812.2851, 2008.
Floyd, R. W. Algorithm 245: Treesort 3, Communications of the ACM 7 (12) (1964) 701.
Fredman, M. L., Sedgewick, R., Sleator, D. D., Tarjan, R. E. The Pairing Heap: A New Form of Self-adjusting Heap, Algorithmica, 1 (1986), 111–129.
Larkin, D.H., Sen, S., Tarjan, R.E. A Back-to-Basics Empirical Study of Priority Queues / 16th Workshop on Algorithm Engineering and Experiments 2014 (ALENEX14) Portland, Oregon, USA 5 January 2014. Р. 61-73
Peterson, G. L. A balanced tree scheme for meldable heaps with updates. Technical Report GIT-ICS-87-23. School of Information and Computer Science, Georgia Institute of Technology (1987).
Rasmussen, J. Implementing run-relaxed weak queues. Technical Report CPH STL 2008-1, Department of Computing, University of Copenhagen, 2005.
Takaoka, T. Theory of 2-3 Heaps. In Proc. of COCOON 99, vol. 1627 of Lecture Notes in Computer Science, pp.41-50, 1999.
Vuillemin, J. A data structure for manipulating priority queues, Communications of the ACM 21 (4) (1978) 309-315.
Refbacks
- There are currently no refbacks.
Abava Кибербезопасность IT Congress 2024
ISSN: 2307-8162