Monticulos binarios

ABSTRACT

Los Montículos binarios: Son un caso particular y sencillo de la estructura de datos Montículo, y está basada en un árbol binario balanceado, puede verse como un árbol binario con dos restricciones adicionales:
• 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).
• Es un árbolsemicompleto, es decir que el árbol está balanceado y en un mismo nivel las inserciones se realizan de izquierda a derecha.

Algunas operaciones que pueden realizarse son:

• Agregar
• Eliminar
• Formar el Heap

Montículos Binarios (Heap)

El montículo binario es la implementación específica más básica y habitual de una
cola de prioridad.
También es frecuente referirse a él por sunombre en inglés: “( binary) heap”.
Un heap es un árbol binario con dos propiedades adicionales: estructural y de orden.
Estructura de heap. Un heap es un árbol binario casi completo con n nodos.

• Un árbol binario casi completo con n nodos se puede almacenar en un vector con
n o más componentes.
• Numerando los nodos del árbol binario casi completo por niveles, de arriba a abajo
y deizquierda a derecha, cada nodo i del heap se almacena en la posición i del
vector.
• No se necesitan punteros para acceder a los hijos o al padre de un nodo.
• Principal problema: se debe estimar a priori el tamaño máximo del heap.

Dado un nodo cualquiera i, 1 _ i _ n:
• Su hijo izquierdo esta en 2i (si tiene; es decir, si 2i _ n).
• Su hijo derecho está en 2i + 1 (si tiene; es decir, si 2i +1 _ n).
• Su padre está en [ i/2] (si tiene; es decir, si i > 1).

Orden de heap
En un heap, el elemento situado en cada nodo es menor o igual que
el elemento situado en cualquiera de sus hijos (si el nodo tiene algún hijo).

• El elemento mínimo siempre está en la raíz.
• En cada subárbol se verifica el orden de heap.
• El elemento máximo está en una hoja.

Insertar

En un heapde n elementos, al insertar uno nuevo se deberá utilizar la posición n + 1
del vector para mantener la estructura de heap.
Si se preserva el orden de heap al situarlo en el hueco (nodo n+1), fin de la inserción.
Si no, el nuevo elemento será menor que el elemento que está en el padre del hueco.
Se baja el elemento del nodo padre al hueco y ahora el hueco queda en el padre.
Este proceso serepite hasta colocar el nuevo elemento en un hueco. En el peor caso,
el hueco ascenderá hasta la raíz.

Partiendo desde el nodo n + 1 al insertar, la violación del orden de heap solo puede
aparecer en el camino desde este nodo a la raíz, e ira trasladándose a lo largo de él.
Si el elemento de i es menor que el de [i/2] , al intercambiarlos queda el menor como
padre de dos mayores. El delhermano (i − 1 ´o i + 1) ya era mayor que el del padre.
Si el elemento de i debe seguir subiendo a [ [ i/2 ] /2 ], el que baje a [i/2] será menor
que los que había en [i/2] e i − 1 ´o i + 1. Al inicio, el orden de heap se cumplía.

Eliminar Min.

En un heap de n elementos, al eliminar uno se deberá inutilizar la posición n del
vector, dejándolo con n − 1 elementos, para mantener la estructurade heap.
Como el elemento que se elimina es el mínimo y este está en la raíz, inicialmente
tenemos un hueco en la raíz y el elemento que estaba en la posición n por recolocar.
Si se preserva el orden de heap al situar el elemento en el hueco, fin de la eliminación.
Si no (lo más probable), el elemento por recolocar será mayor que alguno de los
elementos que están en los hijos del hueco.

Sesube el menor de los elementos de los hijos al hueco y ahora el hueco queda en
el nodo hijo en el que estaba este menor elemento.
Este proceso se repite hasta recolocar el elemento pendiente en un hueco. En el peor
caso, el hueco descenderá hasta las hojas.

Al eliminar, la violación del orden de heap solo puede aparecer en el camino desde la
raíz a las hojas, e ira trasladándose a lo...