Las dos operaciones básicas de las colas de prioridad son insertar y eliminar mínimo. Vamos a conocer su funcionamiento.
La inserción en una cola de prioridad puede ser algo muy simple o una operación compleja.
Inicialmente se inserta el nuevo elemento en la primera posición libre de la cola de prioridad, en el montículo representado arriba se insertaría como el hijo derecho del nodo C. En el caso de que el nuevo elemento fuese mayor que su padre la operación de inserción habría finalizado, ya que seguiría manteniendo la condición de orden de los montículos. Por supuesto este era el caso simple...
La complejidad se produce cuando el nodo insertado es menor que su padre. Si repasamos las condiciones para que una estructura sea un montículo binario observaremos que es necesario que cada nodo sea menor que sus hijos, por lo que si dejásemos la estructura así, con el nuevo nodo en la última posición, esa estructura ya no sería un montículo.
Para solucionar este problema lo que se realiza es un intercambio entre padre e hijo. Con este intercambio ya estaría solucionado el problema, pero ¿qué sucede si el nuevo nodo (que se ha intercambiado con el padre) es aún más pequeño que su nuevo padre?. Pues la respuesta es simple, se volvería a realizar un nuevo intercambio del nuevo nodo con su nuevo padre, prolongándose estos intercambios hasta que el nuevo nodo sea mayor que sus padre o hasta que el nuevo nodo llegue a la raíz.
Vamos a ver este caso con un ejemplo gráfico:
Sobre el montículo inicial, representado por los nodos negros, insertamos un nuevo elemento con valor 3, representado por el nodo rojo.
Como vemos, si se dejase en esa posición el nuevo nodo, se violaría la condición de orden del montículo, ya que el nodo 8 no es menor que todos sus descendientes ( 3 es menor que 8). Por lo tanto se realiza un intercambio entre 8 y 3.
La situación ahora entre el nodo 8 y el nodo 3 es correcto. Perfecto. Pero si observamos un poco más arriba, veremos que el nodo padre del nuevo nodo, el 4, viola de nuevo la condicón de orden del montículo. Por lo tanto volvemos a intercambiar posiciones entre 3 y 4.
Ahora sí que ya podemos decir que el montículo es correcto, ya que el nuevo nodo 3 sí que es mayor que la raíz 1.
Véase que la condición de orden sólo obliga a que un nodo sea menor que sus descendientes, no a que sea menor que los nodos que estén en un nivel inferior. Esto se puede apreciar con el hijo izquierdo de 2 ( valor 5) y el nodo con valor 4 situado en el mismo nivel. Nodo 4 es menor que nodo 5 y está en un nivel inferior. Esto no importa, el montículo es correcto.
La operación eliminar mínimo consta de dos partes, la búsqueda del mínimo y su eliminación. La búsqueda es fácil, el mínimo es siempre la raíz. Eliminarlo es lo complejo.
Al eliminar el mínimo se crea un hueco en la raíz, este hueco se cubrirá con el menor de uno de los siguientes nodos, sus hijos o el último nodo del montículo. Al realizar este trasvase, se creará un nuevo hueco en el lugar del nodo que promocionó a la raíz, excepto si el nodo que promocionó fue el último del montículo. Para cubrir este nuevo hueco se vuelve a realizar la misma acción, se cubre con el menor de sus hijos o con el último nodo si éste es más pequeño. Este procedimiento se repetirá recursivamente hasta que el hueco sea cubierto por el último nodo del montículo original, caso que se producirá cuando dicho nodo sea menor que los nodos hijo del hueco o cuando el hueco esté situado en un nodo hoja.
Este proceso se apreciará mejor gráficamente:
Al eliminar el mínimo (1), se crea un hueco en la raíz que será cubierto por el menor de los siguientes nodos: hijo izquierdo (2), hijo derecho (3), último nodo (4). En este caso el nodo que promociona será el 2.
Para ocupar el nuevo nodo se tienen en cuenta los siguientes nodos: hijo izquierdo (5), hijo derecho (8), último nodo (4). El mínimo es el 4, por lo tanto es el que ocupa el hueco y se acaba la operación de inserción. La estructura obtenida es un montículo correcto.
En una cola de prioridad el resto de operaciones son secundarias y cada cola puede implementar unos métodos distintos. Por esta razón no entraré en otras operaciones.
Únicamente comentar que las colas de prioridad pueden ser también de máximos, caso inverso totalmente al visto en esta página. Es importante también advertir que en un montículo de mínimos la operación eliminar máximo no es ni mucho menos tan eficiente como la operación eliminar mínimo, ya que habría que realizar un recorrido completo del árbol para encontrar el máximo. De la misma forma sucede con la operación eliminar mínimo en un montículo de máximos.
