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 formula_1. Also, assuming the last level is full, the number of elements on that level is also formula_1. In fact, because of these properties all basic operations (insert, remove, find) run in formula_3 time on average. Find operations in the heap can be formula_4 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 formula_3 time for the maximum element.
Actually, a formula_3 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.