Beap

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

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

References

• Munro, J. Ian; Suwanda, Hendra (1980). "Implicit data structures for fast search and update". Journal of Computer and System Sciences 21 (2): 236–250. doi:10.1016/0022-0000(80)90037-9.
• Williams, J. W. J. (Jun 1964). "Algorithm 232 - Heapsort". Communications of the ACM 7 (6): 347–348. doi:10.1145/512274.512284.