2-3 Heap

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.