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 más alta.
• estaVacia: Comprueba si la cola está 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 más alta. Lo que son las prioridades y cómo 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.

El método de inicialización, estaVacia, e inserta son todos calcados de las
operaciones sobre listas. El único método interesante es quita:

Al principio de cada iteración, maxi contiene el ı́ndice del elemento más grande (prioridad más alta) que hemos visto hasta el momento. Cada vez que se completa el bucle, el programa compara la variable i del 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.

Añadimos el programa principal al final de la línea:

Nos mostrará los resultados:

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 método __cmp__ .
Cuando la función 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 método __cmp__ trabaje adecuadamete, la Cola Priorizada funcionará.