Haep

En computación, un montículo (heap en inglés) es una estructura de datos del tipo árbol con información perteneciente a un conjunto ordenado. Los montículos máximos tienen la característica de que cada nodo padre tiene un valor mayor que el de todos sus nodos hijos, mientras que en los montículos mínimos, el valor del nodo padre es siempre menor al de sus nodos hijos.
Un árbol cumple lacondición de montículo si satisface dicha condición y además es un árbol binario completo. Un árbol binario es completo cuando todos los niveles están llenos, con la excepción del último, que se llena desde la izquierda hacia la derecha.
En un montículo de prioridad, el mayor elemento (o el menor, dependiendo de la relación de orden escogida) está siempre en el nodo raíz. Por esta razón, losmontículos son útiles para implementar colas de prioridad. Una ventaja que poseen los montículos es que, por ser árboles completos, se pueden implementar usando arreglos, lo cual simplifica su codificación y libera al programador del uso de punteros.
La eficiencia de las operaciones en los montículos es crucial en diversos algoritmos de recorrido de grafos y de ordenamiento (heapsort).Contenido[ocultar] * 1 Operaciones * 1.1 Insertar * 1.2 Eliminar * 2 Véase también |
[editar] Operaciones
Las operaciones más importantes o básicas en un montículo son la de inserción y la de eliminación de uno o varios elementos.
[editar] Insertar

Cómo se inserta un elemento en un montículo.
Monticulus: Esta operación parte de un elemento y lo inserta en un montículo aplicando sucriterio de ordenación.Si suponemos que el monticulo está estructurado de forma que la raíz es mayor que sus hijos, comparamos el elemento a insertar (incluido en la primera posición libre) con su padre.Si el hijo es menor que el padre,entonces el elemento es insertado correctamente, si ocurre lo contrario sustituimos el hijo por el padre.
¿Y si la nueva raíz sigue siendo más grande que su nuevopadre?. Volvemos a hacer otra vez dicho paso hasta que el montículo quede totalmente ordenado. En la imagen adjunta vemos el ejemplo de cómo realmente se inserta un elemento en un montículo. Aplicamos la condición de que cada padre sea mayor que sus hijos, y siguiendo dicha regla el elemento a insertar es el 12. Es mayor que su padre, siguiendo el método de ordenación, sustituimos el elemento por supadre que es 9 y así quedaría el montículo ordenado.
Ahora veremos la implementación en varios lenguajes de programación del algoritmo de inserción de un elemento en un montículo.
En Maude el insertar se realiza a través de un constructor:
op insertarHeap : X$Elt Heap{X} -> HeapNV{X}

eq insertarHeap(R, crear) = arbolBin(R, crear, crear).

eq insertarHeap(R1, arbolBin(R2, I, D)) =

if ((altura(I) > altura(D)) and not estaLleno?(I))

or (((altura(I) == altura(D)) and estaLleno?(D))

then arbolBin(max(R1, R2),insertarHeap(min(R1, R2), I), D)else arbolBin(max(R1, R2), I,insertarHeap(min(R1, R2), D))

fi .
En pseudolenguaje quedaría:

PROC Flotar ( M, i )

MIENTRAS (i>1) ^ (M.Vector_montículo[i div 2] < M.Vector montículo[i] HACERintercambiar M.Vector montículo[i div 2] ^ M.Vector_montículo[i]
i = i div 2
FIN MIENTRAS

FIN PROC

PROC Insertar ( x, M )

SI M.Tamaño_montículo = Tamaño_máximo ENTONCES

error Montículo lleno...