# Beap

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