Cola con Prioridad en C#

Ene 31, 2011 Codigos C# Tutoriales C# 4 comentarios

Cuando hablamos de colas con prioridad hablamos de una lista de elementos ordenados según su prioridad, que es una función asignada a cada elemento de la cola.

La estructura cola (queue) está basada en el principio que plantea que “el primero en entrar a la cola es el primero en salir (First In First Out), de aquí que a estas estructuras se le llaman (FIFO). En este caso no se va a cumplir este principio, ya que los elementos van a estar ordenados en función de la prioridad. Las operaciones que definiremos sobre una cola con prioridad son:

Insertar – Inserta un elemento en la cola con prioridad. Luego de esta operación, el elemento insertado estará en su posición de acuerdo con su prioridad.

Extrae-Min (Extrae-Max) – Extrae el elemento de mayor prioridad de la cola.

Devuelve-Min (Devuelve-Max) – Retorna el elemento de mayor prioridad, pero no lo elimina.

Esta estructura pudiera ser útil, por ejemplo, en la sala de urgencia de un hospital, donde cada paciente debe ser atendido en función de su gravedad. Luego, con esta estructura podríamos formar un orden entre los pacientes logrando que los pacientes mas graves fueran atendidos primero.

Existen diversas formas de implementar esta estructura, pero en casi todas, alguna de las operaciones principales (ExtraeMin o Insertar) son de orden lineal respecto a la cantidad n de elementos que se almacenan. En este post, veremos cómo lograr una buena implementación de esta estructura usando un tipo de árbol binario que cumple ciertas características, llamado Árbol Parcialmente Ordenado (Heap), donde ambas operaciones serán O(log(n)). Veamos formalmente que es un heap.

Que es un Heap?

Un Heap es un árbol que tiene las siguientes características:

i. Es un árbol binario.
ii. Todos los niveles están llenos, excepto, quizás, el último.
iii. Los niveles se van llenando de izquierda a derecha. Si el árbol no es completo, en el último nivel, las hojas están agrupadas a la izquierda.
iv. Cada nodo tiene una prioridad mayor que la de sus dos hijos.

heap Cola con Prioridad en C#

Heap como árbol parcialmente ordenado

Lo primero que podemos ver es que puede haber varios elementos con una misma prioridad, y lo segundo es que el árbol no está ordenado completamente, es decir, entre sus hijos no hay prioridad. Como vimos en el post anterior con los arboles binarios de búsquedas, donde el hijo izquierdo tenía que ser menor que el padre y este a su vez, menor que el hijo derecho. De aquí que este tipo de árbol binario se conoce como Árbol Parcialmente Ordenado, porque no define un orden total entre sus nodos.

Como hablamos de un árbol binario, podríamos pensar en representar un Heap con un arreglo donde A[0] es la raíz del árbol, el hijo izquierdo del nodo i será A[2*i+1] y el derecho A[2*i+2].

Operaciones con el Heap

Veamos ahora como serían los métodos para garantizar que las operaciones sean O(log(n)):
DEVUELVE-MIN(Heap h)
1 if(count(h)>0)
2  do return A[0]

Claramente este primer método es bastante sencillo, ya que el elemento de mayor prioridad siempre va a ser la raíz

EXTRAE-MIN(Heap H)
1  Intercambiar(0,n);
2  H[n] ←null;
3  n←n+1
HEAPIFY( 0);

En Extrae-Min lo que hacemos es eliminar el nodo raíz y poner el ultimo nodo a la derecha del primer nivel como raíz, disminuimos la cantidad de elementos y llamamos a un método llamado recursivo heapify que será el encargado de ubicar al elemento A[0] en su posición de acuerdo a su prioridad. Para esto, lo que hace es en cada paso del algoritmo ver si se viola alguna de las condiciones, y en caso positivo, lo intercambiar con el hijo de menor prioridad, esto es lo que hace que las operaciones sean O(log(n)), veamos un pseudocódigo para ilustrar mejor la idea:

HEAPIFY (Heap H, nodo i)
1  if(i<left(i) and i<right(i))
2  do return;
3  max = Max(left(i), right(i);
Intercambiar(i,max);
Heapify(H, max);

Luego, el método Insert(Heap H, x) sería agregar el nuevo elemento al final del array que representa el Heap y hacer heapify, pero en este caso en el orden contrario, desde las hojas hacia la raíz. A continuación el pseudocódigo:

INSERT(Heap H, x)
1  n←n+1
2  H[n] ←x;
HEAPIFY( n);

Esto es básicamente una buena implementación de Heap con array, que mejora un poco la representación por Arbol, ya que para insertar un nuevo elemento, nos evitamos el trabajo de buscar cual es la hoja más a la derecha, que como sabemos, en la representación por array será el nodo de la posición n.

Código en C# de un Heap

Bueno, aquí les dejo una implementación de Heap en C# que hice el año pasado como parte de una tarea. El código está bien comentado y entendible. De cualquier forma, si ves algún error o tienes alguna duda, en los comentarios. Otra implementación que he usado es proyectos más grandes es la que ofrecen en CodeProjects, que es una clase PriorityQueue mucho más completa, con más métodos y propiedades.

Compartir:

Relacionados

algunos artículos que te pueden interesar

4 comentarios

Forma parte de nuestra discusión y síguela de cerca

Muy interesante, pero tengo una duda de como realizarlo en windows form , sin metodos, y en una estructura de datos..
Gracias

Autor: Hans Gonzalez | Fecha: Nov 7, 2011.

me gustaria que me ayudes en un trabajo, tengo q presentar un codigo de “colas” en cual debo de eliminar el mayor elemento de lo que e ingresado

Autor: KAREN | Fecha: Ene 26, 2012.

lo siento pero no pude hacer correr tu programa, puedes ayudarme con eso, me parecio muy interesante tu explicacion

Autor: KAREN | Fecha: Ene 26, 2012.

@KAREN, más bien parece que buscas eliminar un elemento en un array, no veo la necesidad de usar una “cola” para ese ejercicio, puedes usar arrays. Mira en este post está el de Insertar un elemento, solo tienes que hacer un par de cambios para resolver tu problema:
Ejericios resueltos de array con C#

Autor: Tomy | Fecha: Ene 28, 2012.

Escribe tu comentario

Requerido.

Requerido. No público.

Si tienes alguno.