2-3 Heap

Konstantin V. Gulakov

Abstract


Heap data structures have recently received significant development and are very diverse. 2-3 heap is one of the representatives of the pyramids at the base of the forest of trees. The advantage of a 2-3 tree is that the hard height constraint log(n) is compensated by balancing in width (horizontal balancing). This allows to have a minimum tree height and thus increase the performance of some operations. Tadao Takaoka proposed a pyramidal modification of these trees and combining them into a 2-3 heap. The study of this work leaves many questions on the implementation of 2-3 heaps and operations on it. While the merits of this structure are obvious, it is possible that these difficulties prevented its popularity among programmers. In the present work, a complete understanding of this structure is carried out, primarily in terms of its implementation and operations on it, which fills the gap in the Russian-language literature.


Full Text:

PDF (Russian)

References


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

Driscoll, J.ft., H.N. Gabow, ft. Shrairman, and R.E. Tarjan, An alternative to Fibonacci heaps with application to parallel computation, Comm. ACM, 31(11) (1988) 1343-1345.

Fredman, M.L. and R,E, Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Jour. ACM 34 (1987) 596-615

Takaoka, T.. Theory of 2-3 Heaps.— Cocoon (1999), p.41-50


Refbacks

  • There are currently no refbacks.


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

ISSN: 2307-8162