Sobre la implementación de montículos
La implementación habitual (vista en clase, transparencia 16) de un montículo es estática, es decir, basada en almacenar el árbol en un vector, por niveles, desde la raíz hacia abajo y de izquierda a derecha para cada nivel.
Lógicamente, esa implementación plantea el típico problema (en representaciones estáticas) de saturación cuando la capacidad del vector se completa.
Hay una solución para ese problema. Se basa en tener un vector de punteros a vectores de datos en el que inicialmente sólo se usa el primer puntero a vector, y apunta a un montículo almacenado como el visto en clase (en el vector, por niveles de arriba a abajo y de izquierda a derecha). Cuando ese primer vector de datos se llena, se usa el siguiente puntero a vector para apuntar a un nuevo vector en el que se guardará el siguiente nivel del montículo. Si ese nivel también se llena, se genera espacio para un nuevo nivel (puntero a un nuevo vector), etcétera.
Está explicado en esta página.
