Beap

Un beap , o montón biparental , es una estructura de datos para un conjunto (o mapa, o multiconjunto o multimapa) que permite localizar, insertar o eliminar elementos (o asignaciones) en tiempo sublineal . En un beap, cada elemento se almacena en un nodo con hasta dos padres y hasta dos hijos, con la propiedad de que el valor de un nodo padre nunca es mayor que el valor de ninguno de sus hijos.

Los beaps se implementan utilizando un array que contiene únicamente los valores que se van a almacenar, y las relaciones padre-hijo se determinan implícitamente mediante los índices del array. (Es decir, los beaps son una estructura de datos implícita ). En este sentido, son similares a los montículos binarios , que también suelen implementarse de esa manera. Sin embargo, sus características de rendimiento difieren de las de los montículos; en particular, un beap permite la recuperación sublineal de elementos arbitrarios.

El beap fue introducido por Ian Munro y Hendra Suwanda . Una estructura de datos relacionada es el tableau de Young .

La altura de la estructura es aproximadamente${\displaystyle {\sqrt {n}}}$. Además, suponiendo que el último nivel esté lleno, el número de elementos en ese nivel también es${\displaystyle {\sqrt {n}}}$De hecho, debido a estas propiedades, todas las operaciones básicas (insertar, eliminar, buscar) se ejecutan en${\displaystyle O({\sqrt {n}})}$tiempo en promedio. Las operaciones de búsqueda en el montón pueden ser${\displaystyle O(n)}$en el peor de los casos. La eliminación e inserción de nuevos elementos implica la propagación de elementos hacia arriba o hacia abajo (de forma similar a un montón) para restaurar el invariante de beap. Una ventaja adicional es que beap proporciona acceso en tiempo constante al elemento más pequeño y${\displaystyle O({\sqrt {n}})}$tiempo para el elemento máximo.

En realidad, un${\displaystyle O({\sqrt {n}})}$La operación de búsqueda se puede implementar si se mantienen punteros al nodo padre en cada nodo. Se comienza en el elemento más bajo del nodo superior (similar al hijo más a la izquierda en un montón) y se avanza hacia arriba o hacia la derecha para encontrar el elemento de interés.

• Munro, J. Ian; Suwanda, Hendra (1980). "Estructuras de datos implícitas para búsqueda y actualización rápidas" . Journal of Computer and System Sciences . 21 (2): 236– 250. doi : 10.1016/0022-0000(80)90037-9 .
• Williams, JWJ (junio de 1964). "Algoritmo 232 - Heapsort". Communications of the ACM . 7 (6): 347– 348. doi : 10.1145/512274.512284 .