Estructuras de datos dinámicas/Colas de prioridad y montones
Colas de prioridad y montones
editarUna 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
editarUn montículo es un árbol binario que satisface las siguientes condiciones:
Operaciones
editarInsertar
editarEl 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
editarSuprimir 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()
editarAñ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()
editarRestablece 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
editarUn á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:
Ordenación mediante montones (Heapsort)
editarSe 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
editarUn montículo binomial es similar a un montículo binario, pero soporta eficientemente la fusión de dos montículos.
Árbol Binomial
editarDefinició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 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
editarUn montículo binomial se implementa como un conjunto de árboles binomiales que satisfacen las propiedades del montículo:
Operaciones
editarFusión
editarComo 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
editarLa 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
editarPara 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
editarLuego 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
editarLuego 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
editarPara 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
editarLas siguientes operaciones se ejecutan en un tiempo de O(log n) en un montículo binomial con n elementos:
Implementación
editarComo 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.