Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Unidad 3/Colas de prioridad y montones

Colas de prioridad y montones

Una cola de prioridad soporta acceso y eliminación del elemento de mayor prioridad: primero() y suprimir(). Puede implementarse como una lista ordenada por prioridad, cuya complejidad para el caso peor en la operación insertar es O(N), un árbol binario de búsqueda, con complejidad media en las operaciones primero() y suprimir(): O(log N), o un árbol binario de búsqueda equilibrado.

Montículo binario, montón o heap

Un montículo es un árbol binario que satisface las siguientes condiciones:

Es completo, con la excepción del nivel inferior, que debe llenarse de izquierda a derecha.

Las hojas están en dos niveles adyacentes.

Para cada nodo X con padre P, se cumple que el dato en P es mayor o igual que el dato en X. Ventajas:

Soporta las operaciones insertar y suprimir en tiempo O(log N) en el caso peor.

Soporta insertar en tiempo constante en promedio y primero en tiempo constante en el peor caso.

Operaciones

Insertar

El procedimiento comienza con la creación de un hueco en la siguiente posición disponible del vector. El elemento se coloca si no se viola la propiedad de ordenación del montículo. Si no, se desplaza el elemento situado en el padre del nodo a dicho hueco. Se continúa con el proceso hasta que se pueda colocar el elemento.

Suprimir

Suprimir un elemento de la cola de prioridad consiste en eliminar la raíz. La eliminación del elemento con prioridad mayor implica colocar el último elemento en un hueco que se crea en la raíz. El hueco se hunde en el árbol a través de los hijos con prioridad mayor hasta que el elemento se pueda colocar sin violar la propiedad de ordenamiento del montículo.

Método introducir()

Añade un objeto a la cola de prioridad, pero no garantiza que se mantenga la propiedad de ordenación del montículo.

Método privado arreglarMontículo()

Restablece el orden en el montículo. Llama al método hundir(int) sobre cada nodo en sentido inverso al recorrido por niveles, cuando se realice la llamada con el nodo i se habrán procesado todos los descendientes del nodo i con una llamada a hundir(). No hace falta ejecutar hundir sobre las hojas, por lo que se comienza con el nodo de mayor índice que no sea una hoja.

Implementación de un montículo

Un árbol binario completo se puede representar usando un array, colocando la raíz en la posición 1 y almacenando su recorrido por niveles en el vector. Dado un elemento en la posición i del vector:

Hijo izquierdo: posición 2i,

Hijo derecho: posición 2i +1

Padre: posición i/2 (parte entera) Se necesita mantener un entero que indique cuántos nodos hay actualmente en el árbol.

Ordenación mediante montones (Heapsort)

Se puede usar una cola de prioridad para ordenar N elementos insertándolos en un montículo binario y extrayéndolos llamando a suprimir() N veces. O(N log N) en el caso peor.

Montículo binomial

Un montículo binomial es similar a un montículo binario, pero soporta eficientemente la fusión de dos montículos.

Árbol Binomial

Definición recursiva: Un árbol binomial de orden 0 es un nodo. Un árbol binomial de orden k tiene una raíz de grado k y sus hijos son raíces de árboles binomiales de orden k-1, k-2, ..., 2, 1, 0 (en ese orden). Un árbol binomial de orden k tiene 2k nodos, y altura k. Por su estructura, un árbol binomial de orden k puede ser construido a partir de dos árboles de orden k-1 en forma trivial, agregando uno de ellos como el hijo más a la izquierda del otro.

Estructura de un montículo binomial

Un montículo binomial se implementa como un conjunto de árboles binomiales que satisfacen las propiedades del montículo:

Cada árbol binomial en el montículo cumple la propiedad de montículo: la prioridad de un nodo es menor que la de su padre.

Puede haber como máximo un árbol binomial de cada orden. La segunda propiedad implica que un montículo binomial con n elementos contiene lg(n+1) –logaritmo binario de n+1- árboles binomiales como máximo. de hecho, el número y los órdenes de estos árboles está determinado por n: cada árbol corresponde al dígito menos significativo en la representación binaria de n. Por ejemplo, 13 es 1101 en binario, $2^{3}+2^{2}+2^{0}$, y el montículo binomial con 13 elementos consistirá en tres árboles binomiales de órdenes 3, 2, y 0.

Operaciones

Fusión

Como el nodo raíz tiene el elemento con mayor prioridad del árbol, comparando las claves de las raíces, se obtiene la de mayor prioridad, que será la clave del nodo raíz. Entonces, el otro árbol se convierte en un subárbol del árbol combinado. Si uno solo de los montículos contiene un árbol de orden j, éste árbol se lleva el montículo fusionado. Si ambos montículos contienen un árbol de orden j, ambos árboles son fusionados en uno de orden j+1 de tal manera que la propiedad de montículo se cumpla. Más tarde puede hacer falta fusionar este árbol con otro de orden j+1 presente en alguno de los montículos. En la ejecución del algoritmo, se deben examinar como máximo tres árboles de cada orden (dos provenientes de cada montículo fusionado y uno compuesto de dos árboles más pequeños). Cada árbol tiene como máximo orden lg n, por lo tanto su tiempo de ejecución es de O(lg n).

Inserción

La inserción de un nuevo elemento dentro de un montículo puede realizarse simplemente creando un nuevo montículo que contenga sólo dicho elemento, y fusionar este nuevo montículo con el original en tiempo de O(lg n).

Encontrar Primero

Para encontrar el elemento con mayor prioridad del montículo, simplemente debe buscarse el mínimo entre las raíces de los árboles binomiales, lo cual puede realizarse en un tiempo de O(lg n).

Eliminar Primero

Luego de buscar el elemento entre las raíces de los árboles binomiales, tomar los subárboles del nodo encontrado, reordenarlos de modo de formar otro montículo binomial, y fusionarlo con el montículo original.

Incrementar prioridad

Luego de incrementar la prioridad de un elemento, puede resultar con mayor prioridad que su padre, violando la propiedad de montículo. Si es ese el caso, debe intercambiarse la posición del elemento con la de su padre, sucesivamente hasta que se cumpla la propiedad de montículo. Cada árbol binomial tiene lg n de altura como máximo, de manera que toma un tiempo del O(lg n).

Eliminar

Para eliminar un elemento cualquiera del montículo, debe incrementarse su prioridad de manera que sea la mayor del montículo, y luego ejecutar la operación Eliminar Primero.

Resumen de la complejidad de las operaciones

Las siguientes operaciones se ejecutan en un tiempo de O(log n) en un montículo binomial con n elementos:

Insertar un nuevo elemento

Encontrar el elemento con mayor prioridad

Eliminar el elemento con mayor prioridad

Incrementar la prioridad de un elemento

Eliminar un elemento cualquiera

Fusionar con otro montículo

Implementación

Como ninguna operación requiere acceso aleatorio a las raíces de los árboles binomiales, éstas pueden ser almacenadas en una lista enlazada, ordenada en forma creciente de acuerdo al orden del árbol.