Un beap , o montón biparental , es una estructura de datos para un conjunto (o mapa, o multiconjunto o multimapa) que permite ubicar, insertar o eliminar elementos (o mapeos) 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 cualquiera de sus hijos.
Los beaps se implementan utilizando una matriz que contiene solo los valores que se almacenarán, y las relaciones padre-hijo se determinan implícitamente mediante los índices de la matriz. (Es decir: los beaps son una estructura de datos implícita ). En ese sentido, son similares a los montículos binarios , que normalmente también se implementan de esa manera. Sin embargo, sus características de rendimiento son diferentes a las de los montículos; en particular, un beap permite la recuperación sublineal de elementos arbitrarios.
Ian Munro y Hendra Suwanda introdujeron el beap . Una estructura de datos relacionada es la tabla de Young .
La altura de la estructura es de aproximadamente . Además, suponiendo que el último nivel está lleno, la cantidad de elementos en ese nivel también es . De hecho, debido a estas propiedades, todas las operaciones básicas (insertar, eliminar, buscar) se ejecutan en el tiempo en promedio. Las operaciones de búsqueda en el montón pueden ser 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 (muy similar a un montón) para restaurar la invariante de beap. Una ventaja adicional es que beap proporciona acceso en tiempo constante al elemento más pequeño y tiempo para el elemento más grande.
En realidad, se puede implementar una operación de búsqueda si se mantienen los punteros padre en cada nodo. Se comenzaría en el elemento más inferior del nodo superior (similar al elemento hijo más a la izquierda en un montón) y se avanzaría hacia arriba o hacia la derecha para encontrar el elemento de interés.
