Layered Heap

Abstract

The article is devoted to one of the varieties of the binomial heap, a multilevel heap widely used in solving various problems. A brief comparison of it with the most effective pyramidal structures made it possible to formulate the goals of this structure and the ways to achieve them. Unlike the existing ones, the heap is characterized by the minimum complexity order O of the operation of removing the minimum element from the heap due to the reduction in the number of comparison operations. The article discusses various options for implementing a multi-level heap due to some change in binomial trees. The first option assumes the presence of upper, lower levels and a heap storage, due to which compensation of deleted elements occurs and the number of operations to restore the heap at the lower level is reduced. The second implementation involves the abandonment of the store, but instead of binomial trees, similar to binomial F-trees are introduced. The resulting F-Heap allows you to perform the removal and deletion of a minimal element with complexity O. The possibility of further improvement of this structure is shown.