1

Colas de Prioridad• El TDA cola de prioridad• Implementación de una cola de prioridad con una secuencia• Ordenamiento elemental• Asuntos en ordenamiento

2

Llaves y Relaciones de Orden Total

• Una Cola de Prioridad clasifica sus elementos por la key con una relación de orden total

• Llaves:Cada elemento tiene su propia llaveLas llaves no son necesariamente únicas

• Relación de Orden Total, indicado por Reflexiva: k kAntisimetria: si k1 k2 y k2 k1, entonces k1 k2Transitiva: si k1 k2 y k2 k3, entonces k1 k3

• Una Cola de Prioridad soporta estos métodos fundamentales sobre pares de elementos llave:min()insertItem(k, e) removeMin()

3

Ordenación con una Cola de Prioridad

• Una Cola de Prioridad P se puede usar para ordenar una secuencia S mediante:– insertando los elementos de S en P con una serie de operaciones

insertItem(e, e)– extrayendo los elementos de P en orden creciente y colocandolos

nuevamente en S con una serie de operaciones removeMin()Algorithm PriorityQueueSort(S, P):

Input: Secuencia S con n elements, y una cola de prioridadP

Output: Secuencia S ordenada por una relación de orden totalwhile !S.isEmpty() do

e S.removeFirst()P.insertItem(e, e)

while P is not empty doe P.removeMin()S.insertLast(e)

4

TDA para Cola de Prioridad

• Una cola de prioridad P soporta los siguientes métodos:-size(): Devuelve el número de elementos en P-isEmpty(): Comprueba si P está vacía-insertItem(k,e): Inserta un nuevo elemento e con llave k en P-minElement(): Devuelve (sin borrar) un elemento de P

con menor llave; ocurre un error si P está vacía.-minKey(): Devuelve la menor llave en P; ocurre un error si P está

vacía-removeMin(): Extrae de P y devuelve el elemento con menor llave;

ocurre un error si P está vacía

5

Comparadores• La forma más general y reusable de una cola de prioridad hace uso de

objetos comparadores.• Objetos Comparadores son externos a las llaves que se comparan y

comparan dos objetos.• El TDA comparador incluye:

-isLessThan(a, b)-isLessThanOrEqualTo(a,b)-isEqualTo(a, b)-isGreaterThan(a,b)-isGreaterThanOrEqualTo(a,b)-isComparable(a)