19.5. Cola priorizada

El TAD Cola Priorizada tiene el mismo interfaz que el TAD Cola, pero diferente semántica. De nuevo, el interfaz es:
__init __: Inicializa una cola vacía nueva.

inserta: Añade un nuevo elemento a la cola.

quita: Elimina y devuelve un elemento de la cola. El elemento devuelto es el de prioridad mas alta.

estaVacia: Comprueba si la cola esta vacía.

La diferencia semántica es que el elemento eliminado de la cola no es necesariamente el primero que se añadió. En su lugar, es el elemento con la prioridad mas alta. Lo que son las prioridades y como se comparan con las otras no se especifica en la implementación de la Cola Priorizada. Depende de los elementos de la cola.

Por ejemplo, si los elementos de la cola tienen nombres, podemos elegirlos en orden alfabético. Si son puntuaciones de bolos, podemos ir de mayor a menor, pero si son puntuaciones de golf, iremos de menor a mayor. Siempre que podamos
comparar los elementos de la cola, podremos encontrar y quitar el elemento con mayor prioridad.

Esta implementación de Cola Priorizada tiene como atributo una lista de Python que contiene los elementos de la cola.

   1: class ColaPriorizada:

   2:     def __init__(self):

   3:         self.elementos = []

   4:     def estaVacia(self):

   5:         return self.elementos == []

   6:     def inserta(self, elemento):

   7:         self.elementos.append(elemento)

 

El metodo de inicializacion, estaVacia, e inserta son todos calcados de las operaciones sobre listas. El único metodo interesante es quita:

   1: class ColaPriorizada:

   2: ...

   3:     def quita(self):

   4:         maxi = 0

   5:         for i in range(1,len(self.elementos)):

   6:         if self.elementos[i] > self.elementos[maxi]:

   7:         maxi = i

   8:         elemento = self.elementos[maxi]

   9:         self.elementos[maxi:maxi+1] = []

  10:         return elemento

 

Al principio de cada iteración, maxi contiene el índice del elemento mas grande
(prioridad mas alta) que hemos visto hasta el momento. Cada vez que se com-
pleta el bucle, el programa compara el iésimo elemento con el campeón. Si el
nuevo elemento es mayor, el valor de maxi se fija a i.
Cuando la sentencia for completa su ejecución, maxi es el índice del elemento
mayor. Este elemento se elimina de la lista y se devuelve.

Vamos a probar la implementación:

   1: >>> c = ColaPriorizada()

   2: >>> c.inserta(11)

   3: >>> c.inserta(12)

   4: >>> c.inserta(14)

   5: >>> c.inserta(13)

   6: >>> while not c.estaVacia(): print c.quita() # ver cu¶al se quita

   7: 14

   8: 13

   9: 12

  10: 11

 

Si la cola contiene números o cadenas simples, se eliminan en orden numérico o alfabético, de mayor a menor. Python puede encontrar el entero o la cadena mayor porque puede compararlos usando los operadores de comparación internos.

Si la cola contiene un tipo de objeto, debe proporcionar un metodo __cmp__ . Cuando quita usa el operador > para comparar elementos, invoca al __cmp__ de uno de los elementos y le pasa el otro como parámetro. Siempre que el metodo __cmp__ trabaje adecuadamente, la Cola Priorizada funcionara.