Quake heap

V.K. Gulakov, K.V. Gulakov

Abstract


The article is devoted to one of the varieties of pyramidal data structures widely used in solving various problems. Issues improving of software productivity due to use effective pyramidal data structures are discussed. A brief overview of pyramidal structures knowledge development shows regularity of the appearance such structures as a quake heap, which allows performing basic operations on data with minimal complexity. The article gives a detailed description of quake heap structure and gives examples of operations on it and its complexity. It is indicated to feature of improving efficiency due to use the corresponding coefficient. Comparison of the theoretical complexity operations over various pyramidal structures with operations over a quake heap indicates that it is not inferior in efficiency to most popular and effective pyramids, but differs relative simplicity and the ability to restore its effective structure after many operations. The article outlines the ways of its experimental research in various situations and practical problems.


Full Text:

PDF (Russian)

References


Gulakov, V.K. Mnogomernye struktury dannyh. Monografija / V.K. Gulakov, A.O. Trubakov – Brjansk: BGTU, 2010. – 387 s.

Brodnik. A., Lopez-Ortiz, A., Raman, V., Viola, A.. Space-Efficient Data Structures, Streams, and Algorithms / Springer Heidelberg Dordrecht London NewYork 2013 Library of Congress Control Number: 2013944678, 363p

Brodal, G. S.. Fast meldable priority queues. In Proc. 4th International Workshop Algorithms and Data Structures, volume 955 of Lecture Notes in Computer Science, Springer, 1995. p. 282–290.

Brodal, G. S.. Worst-case efficient priority queues. In Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 1996. p 52–58.

Carlsson, S., Munro J. I., Poblete P. V.. An implicit binomial queue with constant insertion time. In Proc. 1st Scandinavian Workshop on Algorithm Theory, volume 318 of Lecture Notes in Computer Science, Springer, 1988. p. 1–13.

Crane, C. A. Linear lists and priority queues as balanced binary trees. PhD thesis, Stanford University, Stanford, CA, USA, 1972.

Chan, Timothy M.. Quake Heaps: A Simple Alternative to Fibonacci Heaps Manuscript, 2009.

Driscoll, J. R. Gabow, H. N. Shrairman, R. Tarjan. R. E. Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Communications of the ACM, 31(11):, 1988. p. 1343–1354

Elmasry, A. Layered heaps. In Proc. 9th Scandinavian Workshop on Algorithm Theory, volume 3111 of Lecture Notes in Computer Science, Springer, 2004. P. 212–222.

Elmasry, A. Parameterized self-adjusting heaps. J. Algorithms, 52(2):103–119, 2004.

Elmasry, A The violation heap: A relaxed Fibonacci-like heap. In Proc. 16th Annual International Conference on Computing and Combinatorics, volume 6196 of Lecture Notes in Computer Science, pages 479–488. Springer, 2010.

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

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

Haeupler, B. Sen, S. Tarjan. R. E. Rank-pairing heaps. In Proc. 17th Annual European Symposium on Algorithsm, v. 5757 of Lecture Notes in Computer Science, Springer, 2009. SIAM Journal of Computing, to appear. p. 659–670.

Høyer. P. A general technique for implementation of efficient priority queues. In Proc. Third Israel Symposium on the Theory of Computing and Systems, , 1995. p. 57–66

Kaplan, H. Tarjan, R. E.. New heap data structures. Technical report, Department of Computer Science, Princeton University, 1999.

Kaplan, H. Tarjan, R. E.. Thin heaps, thick heaps. ACM Transactions on Algorithms, 4(1), 2008.

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 R. 61-73

Mulzer, W., Quake Heaps Erdbebenhaufen http://page.mi.fu-berlin.de/mulzer/

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.

William J. Algorithm 232: Heapsort. Communications of the ACM, 7(6):, 1964. p. 347–348


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162