Montículo (Programación)

En computación, un montículo (heap en inglés) es una estructura de Árbol con información perteneciente a un conjunto ordenado. Los montículos tienen la característica de que cada nodo tiene un valor mayor que el de todos sus nodos hijos.

Montículo binario

Los Montículos binarios (binary heaps en inglés) son un caso particular y sencillo de la estructura de datos Montículo que está basada en un árbol binario balanceado, que puede verse como un árbol binario con dos restricciones adicionales:

• Propiedad de montículo:Cada nodo contiene un valor superior al de sus hijos (para un montículo por máximos) o más pequeño que el de sus hijos (para un montículo por mínimos).

• Árbol semicompleto: El árbol está balanceado y en un mismo nivel las inserciones se realizan de izquierda a derecha.

1 11

 / \ / \

 2 3 9 10

 / \ / \ / \ / \

 4 5 6 7 5 6 7 8

 / \ / \ / \ / \

 8 9 10 11 1 2 3 4

El orden de los nodos hermanos en un montículo no está especificado en la propiedad de montículo, de manera que los subárboles de un nodo son intercambiables.

Operaciones sobre montículos 

Inserción de un elemento

La inserción de un elemento se realiza agregando el elemento en la posición que respeta la restricción de árbol semicompleto pero posiblemente invalidando la propiedad de montículo, para luego remontar hacia la raíz restaurando la  propiedad de montículo por intercambio del valor de la posición desordenada por el valor de su padre. Esta reorganización se realiza en tiempo O(log n).

Eliminación del elemento máximo 

Para borrar el elemento máximo del montículo, de la manera más eficiente se puede tomar el elemento de la posición que debe quedar vacía, colocándolo en la raíz (así cumpliendo la propiedad de árbol completo), y luego intercambiar ese valor con el máximo de sus hijos hasta satisfacer la propiedad de montículo (si es de máximos), o intercambiarlo con el mínimo de sus hijos (si es de mínimos). Esta reorganización se puede realizar también en tiempo O(log n). Partiendo del mismo montículo que antes:

 11

 / \

 5 8

 / \ 

3 4 

Al eliminarse el 11, éste se remplaza por 4 (el valor del nodo que se debe eliminar):

 4

 / \

 5 8

 / 

3

Representación de montículos 

Si bien se puede utilizar un árbol binario para representar un montículo, la condición de árbol completo permite representar fácilmente un montículo en un vector colocando los elementos por niveles y en cada nivel, los elementos de izquierda a derecha.Dado que el árbol es completo, no es necesario almacenar apuntadores en el árbol. Siempre se puede calcular la posición de los hijos o la del padre a partir de la posición de un nodo en el arreglo (contando las posiciones del arreglo a partir de cero):

• El nodo raíz se almacena en la posición 0 del arreglo. 

• Los hijos de un nodo almacenado en la posición k se almacenan en las posiciones 2k+1 y 2k+2 respectivamente. 

Se deduce que el padre de un nodo que está en la posición k (k>0) está almacenado en la posición ((k+1) div 2) – 1.