Beap, or bi-parental heap, is a data structure where a node usually has two parents (unless it is the first or last on a level) and two children (unless it is on the last level). Unlike a heap, a beap allows sublinear search. 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
n
. Also, assuming the last level is full, the number of elements on that level is also
n
. In fact, because of these properties all basic operations (insert, remove, find) run in
O
(
n
)
time on average. Find operations in the heap can be
O
(
n
)
in the worst case. Removal and insertion of new elements involves propagation of elements up or down (much like in a heap) in order to restore the beap invariant. An additional perk is that beap provides constant time access to the smallest element and
O
(
n
)
time for the maximum element.
Actually, a
O
(
n
)
find operation can be implemented if parent pointers at each node are maintained. You would start at the absolute bottom-most element of the top node (similar to the left-most child in a heap) and move either up or right to find the element of interest.
