A beap, or bi-parental heap, is a data structure for a set (or map, or multiset or multimap) that enables elements (or mappings) to be located, inserted, or deleted in sublinear time. In a beap, each element is stored in a node with up to two parents and up to two children, with the property that the value of a parent node is never greater than the value of either of its children.
Beaps are implemented using an array containing only the values to be stored, with the parent-child relationships being determined implicitly by the array indices. (That is: beaps are an implicit data structure.) In that respect they are similar to binary heaps, which are usually implemented that way as well. However, their performance characteristics are different from heaps; in particular, a beap enables sublinear retrieval of arbitrary elements.
The beap was introduced by Ian Munro and Hendra Suwanda. A related data structure is the Young tableau.
The height of the structure is approximately
\sqrt{n}
\sqrt{n}
O(\sqrt{n})
O(n)
O(\sqrt{n})
Actually, a
O(\sqrt{n})