Un beap , o montón bi-parental , es una estructura de datos donde un nodo generalmente tiene dos padres (a menos que sea el primero o el último en un nivel) y dos hijos (a menos que esté en el último nivel). A diferencia de un montón, un beap permite una búsqueda sublineal . El beap fue presentado por Ian Munro y Hendra Suwanda . Una estructura de datos relacionada es el cuadro de Young .
Actuación
La altura de la estructura es aproximadamente . Además, asumiendo que el último nivel está lleno, el número de elementos en ese nivel también es. De hecho, debido a estas propiedades, todas las operaciones básicas (insertar, eliminar, buscar) se ejecutan entiempo en promedio. Las operaciones de búsqueda en el montón pueden serEn 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 (como en un montón) para restaurar el invariante de beap. Una ventaja adicional es que beap proporciona acceso constante en tiempo al elemento más pequeño y tiempo para el elemento máximo.
En realidad, un La operación de búsqueda se puede implementar si se mantienen los punteros principales en cada nodo. Comenzaría en el elemento más bajo absoluto del nodo superior (similar al niño más a la izquierda en un montón) y se movería hacia arriba o hacia la derecha para encontrar el elemento de interés.
Referencias
- Munro, J. Ian; Suwanda, Hendra (1980). "Estructuras de datos implícitas para búsqueda y actualización rápidas". Revista de Ciencias de la Computación y Sistemas . 21 (2): 236–250. doi : 10.1016 / 0022-0000 (80) 90037-9 .
- Williams, JWJ (junio de 1964). "Algoritmo 232 - Heapsort". Comunicaciones de la ACM . 7 (6): 347–348. doi : 10.1145 / 512274.512284 .