Montículo binario

Montículo binario
Para otros usos de este término, véase Montículo (desambiguación).

Los Montículos binarios (binary heaps en inglés) son un caso particular y sencillo de la estructura de datos Montículo, y 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.

Los montículos por máximos se utilizan frecuentemente para representar colas de prioridad. A continuación se muestran dos montículos uno por mínimos y otro por máximos que representan el mismo conjunto de valores.

        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.

Contenido

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).

Ejemplo

En el siguiente montículo por máximos la posición donde se puede insertar está marcada con una letra X.

    11
   /  \
  5    8
 / \  /
3  4 X

Para insertar el valor 15 en este montículo, se inserta el valor en la posición marcada con lo cual se invalida la propiedad de montículo dado que 15 es mayor que 8. Para restaurar la propiedad de montículo se intercambia primero el 15 con el 8, obteniéndose el siguiente árbol:

    11
   /  \
  5    15
 / \  /
3  4 8

Sin embargo, la propiedad de montículo todavía no se cumple, dado que 15 es mayor que 11, de manera que hay que realizar un nuevo intercambio:

    15
   /  \
  5    11
 / \  /
3  4 8

El resultado si es un montículo por máximos.

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  

En este árbol no se cumple la propiedad de montículo dado que 8 es mayor que 4. Al intercambiarse estos dos valores se obtiene un montículo:


    8
   /  \
  5    4
 / 
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.

Un árbol binario completo guardado como arrreglo

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).

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • 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:… …   Enciclopedia Universal

  • 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. Este artículo o sección necesita… …   Wikipedia Español

  • Montículo (desambiguación) — El término montículo puede hacer referencia a: Montículo, como la pequeña colina, natural o artificial, que normalmente se encuentra aislada. Montículo, (heap en inglés) es una estructura de datos del tipo árbol con información perteneciente a un …   Wikipedia Español

  • 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

  • Árbol binario de búsqueda — Un árbol binario de búsqueda es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática. Contenido 1 Descripción 2 Operaciones 2.1 Búsqueda …   Wikipedia Español

  • Estructura de datos — En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema. Una estructura de datos… …   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

  • Lectura óptica — La lectura óptica puede ser la utilizada en un Sistema de Discos Compactos, en donde la información se encuentra en código binario, a tamaño microscópico. El Escritor de Cd s (también llamado quemador o CD RW), lo que hace es lo siguiente: En la… …   Wikipedia Español

  • Lectura óptica — ► locución TECNOLOGÍA Reconocimiento por medio de un procedimiento óptico de los caracteres impresos por un dispositivo automático. * * * Puede ser la utilizada en un Sistema de Discos Compactos, en donde la información se encuentra en código… …   Enciclopedia Universal

Compartir el artículo y extractos

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