Montículo (informática)

Montículo (informática)
Para otros usos de este término, véase Montículo (desambiguación).
Este artículo trata sobre la estructura de datos. Para el lugar de donde se asigna memoria dinámica, véase asignación dinámica de memoria.
Ejemplo de montículo.

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 la condició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, los montí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

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.

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 su criterio 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 nuevo padre?. 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 su padre 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] HACER

                intercambiar 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

  SINO M.Tamaño_montículo = M.Tamaño_montículo + 1

             M.Vector_montículo[M.Tamaño montículo] = x

             Flotar ( M, M.Tamaño_montículo )

FIN PROC

En Java el código sería el siguiente:

public void insertItem(Object k, Object e) throws InvalidKeyException {
    if(!comp.isComparable(k))
        throw new InvalidKeyException("Invalid Key");
    Position z = T.add(new Item(k, e));
    Position u;
    while(!T.isRoot(z)) { // bubbling-up
        u = T.parent(z);
        if(comp.isLessThanOrEqualTo(key(u),key(z)))
             break;
        T.swapElements(u, z);
        z = u;
     }
}

Eliminar

En este caso eliminaremos el elemento máximo de un montículo. La forma más eficiente de realizarlo sería buscar el elemento a borrar, colocarlo en la raíz e intercambiarlo por el máximo valor de sus hijos satisfaciendo así la propiedad de montículos de máximos. En el ejemplo representado vemos como 19 que es el elemento máximo es el sujeto a eliminar.

Se puede observar que ya está colocado en la raiz al ser un montículo de máximos, los pasos a seguir son:

  1. Eliminar el elemento máximo (colocado en la raíz).
  2. Hemos de subir el elemento que se debe eliminar, para cumplir la condición de montículo a la raíz, que ha quedado vacía.
  3. Una vez hecho esto queda el último paso el cual es ver si la raíz tiene hijos mayores que ella si es así, aplicamos la condición y sustituimos el padre por el mayor de sus progenitores.

A continuación veremos la especificación de eliminar en distintos lenguajes de programación.

En Maude el código será el siguiente:

eq eliminarHeap(crear) = crear .
eq eliminarHeap(HNV) =
    hundir(arbolBin(ultimo(HNV),
    hijoIzq(eliminarUltimo(HNV)),
    hijoDer(eliminarUltimo(HNV))
)

Donde hundir es una operación auxiliar que coloca el nodo en su sitio correspondiente.

En código Java:

public Object removeMin() throws PriorityQueueEmptyException {
    if(isEmpty())
        throw new PriorityQueueEmptyException("Priority Queue Empty!");
    Object min = element(T.root());
    if(size() == 1)
        T.remove();
    else {
        T.replaceElement(T.root(), T.remove());
        Position r = T.root();
        while(T.isInternal(T.leftChild(r))) {
            Position s;
            if(T.isExternal(T.rightChild(r)) || comp.isLessThanOrEqualTo(key(T.leftChild(r)),key(T.rightChild(r))))
                s = T.leftChild(r);
            else
                s = T.rightChild(r);
            if(comp.isLessThan(key(s), key(r))) {
                T.swapElements(r, s);
                r = s;
            }
            else
                break;
        }
    }
}

Tras haber especificado ambas operaciones y definir lo que es un montículo sólo nos queda por añadir que una de las utilizaciones más usuales del tipo heap (montículo) es en el algoritmo de ordenación de heapsort. También puede ser utilizado como montículo de prioridades donde la raíz es la de mayor prioridad.

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Montículo de Fibonacci — Para otros usos de este término, véase Montículo (desambiguación). En Informática, un Montículo de Fibonacci (o Heap de Fibonacci) es una estructura de datos subconjunto de los montículos, que a su vez, son un subconjunto especial dentro de los… …   Wikipedia Español

  • Desbordamiento de montículo — En informática, un desbordamiento de montículo (heap overflow/overrun) es un problema aritmético que hace referencia al exceso de flujo de datos sobre un montículo, esto permite un acceso no autorizado a la memoria por parte de un comando o de un …   Wikipedia Español

  • Maude — Este artículo o sección sobre informática necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 10 de septiembre de 2008. También… …   Wikipedia Español

  • Cerro de las Minas — Ñuu de la cultura mixteca Lápida de una tumba de Cerro de las Minas …   Wikipedia Español

  • Árbol rojo-negro — Un árbol rojo negro es un tipo abstracto de datos, concretamente es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación. La estructura original fue creada por Rudolf Bayer en… …   Wikipedia Español

  • Desbordamiento de pila — En informática, un desbordamiento de pila (stack overflow/overrun) es un problema aritmético que hace referencia al exceso de flujo de datos almacenados en la pila de una función, esto permite que la dirección de retorno de la pila pueda ser… …   Wikipedia Español

  • Exec Shield — Saltar a navegación, búsqueda Exec Shield es un proyecto realizado por Red Hat, Inc. en 2002 con el objetivo de reducir el riesgo de gusanos u otros ataques automatizados en sistemas Linux. El primer resultado del proyecto fue un parche de… …   Wikipedia Español

  • Zacatelco — La versión original del artículo, o parte de él, procede de Directorio del Estado de Tlaxcala, que edita bajo licencia Creative Commons cc by 2.5 es. Consúltese las restricciones de uso aquí …   Wikipedia Español

  • Municipio de Jiménez (Chihuahua) — Para otros usos de este término, véase Jiménez. Jiménez Municipio de México …   Wikipedia Español

  • Lago de Texcoco — El lago de Texcoco formaba parte de un sistema de lagos, actualmente en proceso de desaparición,[1] localizados al suroeste del valle de México, en el centro del Eje Neovolcánico que atraviesa el territorio nacional desde la costa del Pacífico.[2 …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”