Colas de prioridad
Original: Douglas Wilhelm Harder
Traducido por: Christian von Lücken ([email protected])
Colas de prioridad
Temario
• En este tópico:
– repasaremos sobre colas
– discutiremos el concepto de prioridad
– veremos dos implementaciones simples:
• utilizar un array de colas
• utilizar un árbol AVL
– introducir montículos (heaps), una estructura
de árbol alternativa que tiene mejores
características de tiempo de ejecución
Colas de Prioridad
Colas y Prioridad
• En nuestra implementación de colas:
– el orden de desencolado estuvo basado
estrictamente en el encolado: first in, first out
• En realidad, cada elemento puesto en una
cola puede tener asociado una prioridad
Colas de Prioridad
Prioridad
• Asumimos que la prioridad esta dada por
un entero no negativo (0, 1, 2, ...) donde:
– el valor 0 tiene la prioridad más alta, y
– cuanto menor el número, más alta la prioridad
Colas de Prioridad
Prioridad Lexicográfica
• La prioridad puede depender además de
multiples variables:
– dos valores especifican la prioridad: (a, b)
– un par (a, b) tiene prioridad prioridad más alta
que (c, d) si:
• a < c, o
• a=cyb<d
• Por ejemplo,
– (5, 19), (13, 3), (15, 5), y (15, 2) tienen
prioridad más alta que (15, 7)
Colas de Prioridad
Prioridad de procesos en Unix
• Este es el esquema utilizado en Unix, ej.,
% nice +15 ./a.out
reduce la prioridad de la ejecución del
programa a.out en 15
• Esto permite al procesador ser utilizado
por programas interactivos
• Esto no afecta de manera sigificativa el
tiempo de ejecución de los procesos
asociados a la CPU
Colas de Prioridad
Prioridad de Procesos en Windows
• La prioridad de los
procesos en
Windows puede
asignarse en el
Windows Task
Manager
Colas de Prioridad
Definición
• El encolado es igual para las colas de
prioridad que para las colas
• Sin embargo, desencolar, para una cola:
– Remueve el elemento que ha estadoen la
cola más tiempo
• Para una cola de prioridad:
– Desencolar elimina los elementos con la
prioridad máyor que ha estado en la cola más
tiempo
Colas de Prioridad
Implementación
• Por ejemplo, redefinir enqueue para tomar
un segundo argumento:
template <typename Object>
class PriorityQueue {
private:
// ...
public:
void enqueue( Object obj, int Priority );
// ...
};
Colas de Prioridad
Implementación
• Entonces, podemos usarla como sigue:
PriorityQueue<double> pq;
pq.enqueue( 23.5, 2 );
pq.enqueue( 94.7, 1 );
pq.enqueue( 68.2, 3 );
// encola 23.5 con prioridad 2
// encola 94.7 con prioridad 1
// encola 68.2 con prioridad 3
cout << pq.dequeue() << endl;
cout << pq.dequeue() << endl;
cout << pq.dequeue() << endl;
// imprime 94.7
// imprime 23.5
// imprime 68.2
Colas de Prioridad
Implementación: Múltiples Colas
• Suponga que existe un número fijo de
prioridades, digamos M
• Crear un array de M colas
• Encolar al item con prioridad i en la iésima entrada del array
• Desencolar busca la cola no vacía con
más alta y llama a desencolar en ella
Colas de Prioridad
Implementación: Múltiples Colas
• Ahora las dos operaciones:
head, dequeue
tienen un tiempo de ejecución de O(M)
• Se puede mejorar utilizando árboles?
Colas de Prioridad
Implementación: árboles AVL
• Una implementación es utilizar arboles
AVL
• Ordenar los elementos en base a su
prioridad
• Desencolar debería remover el mínimo
elemento del árbol
Colas de Prioridad
Implementación: árboles AVL
• Problema: múltiples nodos pueden tener
la misma prioridad
• Solución 1:
– en la inserción, si las prioridades son iguales,
siempre insertar el nuevo elemento en el
árbol de la derecha
– solo es útil si es que se está implementando
la cola de prioridad desde el inicio
Colas de Prioridad
Implementación: arboles AVL
• Problema: múltiples nodos pueden tener
la misma prioridad
• Solución 2:
– crear artificialmente un orden único
manteniendo nota sobre un contador de 20bits y utilizando un prefijo con la prioridad
– Incrementar el contador con cada inserción
– crear un orden en cada nivel de prioridad
Colas de Prioridad
Implementación: arboles AVL
• Análisis de tiempo de ejecución:
Función
Función AVL
enqueue(obj,n) insert(obj,n)*
Tiempo de
ejecución
O(ln(n))
head()
front()
O(ln(n))
deenqueue()
remove(front())
O(ln(n))
• Nota: se debe modificar insert de
manera apropiada
Colas de Prioridad
Implementación: Heaps
• Se puede mejorar?
– Esto es, podemos reducir algo (o todas) las
operaciones a O(1)?
• El siguiente tópico define un heap
• Recuerde que un árbol de búsqueda
binario es un tipo especial de árbol binario
• Un heap es tambien un caso especial de
árbol binario pero con una definición
alternativa de orden
Referencias
[1] Cormen, Leiserson, and Rivest, Introduction to
Algorithms, McGraw Hill, 1990, §7.5, p.149.
[2] Weiss, Data Structures and Algorithm Analysis in C++,
3rd Ed., Addison Wesley, Ch.6, p.213.
Usage Notes
• These slides are made publicly available on the web for
anyone to use
• If you choose to use them, or a part thereof, for a course
at another institution, I ask only three things:
– that you inform me that you are using the slides,
– that you acknowledge my work, and
– that you alert me of any mistakes which I made or changes
which you make, and allow me the option of incorporating such
changes (with an acknowledgment) in my set of slides
Sincerely,
Douglas Wilhelm Harder, MMath
[email protected]
Descargar

Priority Queues