Beap

A 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.

Performance

The height of the structure is approximately $\sqrt$. Also, assuming the last level is full, the number of elements on that level is also $\sqrt$. In fact, because of these properties all basic operations (insert, remove, find) run in $O(\sqrt)$ 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(\sqrt)$ time for the maximum element.

Actually, a $O(\sqrt)$ 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.

References

*
* {{cite journal , first=J. W. J. , last=Williams , author-link=J. W. J. Williams , title=Algorithm 232 - Heapsort , date=Jun 1964 , journal=Communications of the ACM , volume=7 , issue=6 , pages=347–348 , doi = 10.1145/512274.512284

Heaps (data structures)