TAD Fila com Prioridade -FCP
ATAI
1
TAD Fila com Prioridade (Priority Queue)
TAD
Fila com Prioridade armazena uma colecção de elementos com
prioridade.
Na
Fila com Prioridade só é possível remover ou aceder ao elemento com
a maior prioridade.
Prioridade é o valor associado a cada elemento e é do tipo ordenado.
Exemplo: Sala de emergência do hospital , onde o doente mais crítico é
atendido primeiro.
É diferente das estruturas de dados posicionais (pilhas, filas, sequencias,
árvores,…), que armazenam elementos em posições específicas de acordo
com inserção e remoção.
Fila com Prioridade armazena elementos de acordo com suas prioridades e
não tem noção de “posição”.
2
Chaves e relação de ordem total

Uma Fila com Prioridade precisa de uma regra de comparação que
defina uma relação de ordem total (). Essa ordem é definida para
cada par de chaves e deve satisfazer as seguintes propriedades:
Reflexiva: k  k
Anti-simétrica: se k1  k2 e k2  k1, então k1 = k2
Transitiva: se k1  k2 e k2  k3, então k1  k3

Uma Fila com Prioridade (P) suporta os seguintes métodos
fundamentais:
min()
insertItem(k, e)
removeMin()
3
Ordenação através de uma FCP
A Fila com Prioridade (P) pode ser usada para ordenar sequencia S:
1.
Introdução elementos de S numa P através de uma série de operações
insertItem (uma para cada elemento de S)
2.
Remoção elementos de P em ordem crescente através de operaçõs
removeMin colocando-os novamente em S em ordem
Algoritmo PriorityQueueSort(S, P):
•Entrada: uma sequencia S que armazena n elementos para os quais uma relação
de ordem total está definida, e a Fila com Prioridade P que compara chaves
usando a mesma relação de ordem total.
•Saida: A sequencia S ordenada pela relação de ordem total.
while !S.isEmpty() do
e  S.removeFirst()
P.insertItem(e, e) {a chave é o próprio elemento}
while !P.isEmpty() do
e  P.removeMin()
S.insertLast(e)
4
TAD Fila com Prioridade
Uma Fila com Prioridade suporta os seguintes métodos:

size()
Retorna o número de elementos em P
Entrada: Nenhuma; Saída: Inteiro

isEmpty()
Testa se P esta vazia
Entrada: Nenhuma; Saída: boolean

insertItem(k,e) Insere um novo elemento e com chave k em P
Entrada: objectos K (chave) e e (elemento); Saída: Nenhuma

minElement() Retorna (sem remover) o elemento de P com menor chave.
Um erro ocorre se o P está vazia.
Entrada: Nenhuma; Saída: Objecto (elemento)

minKey()
Retorna o menor chave em P. Um erro ocorre se o P está vazia.
Entrada: Nenhuma; Saída: Objecto (chave)

removeMin()
Remove de P e retorna o elemento com a menor chave. Um erro
ocorre se o P está vazia.
Entrada: Nenhuma; Saída: Objecto (elemento)
5
Elemento da TAD Fila com Prioridade


O elemento da Fila com Prioridade é do tipo
item
Cada item possui duas partes:


O objecto que define a prioridade (chave) deste
elemento (e que é do tipo comparavel)
O objecto que representa o próprio elemento a
ser guardado na Fila com Prioridade
6
Implementações possíveis do TAD FCP
Uma sequencia não ordenada
Operação insertItem(k,e) permite inserir o elemento no conjunto. A
operação removeMin() é mais complexa, requer a procura de elemento
com a prioridade máxima.
Uma sequencia ordenada (por valores de prioridade)
O elemento com maior prioridade fica posicionado na cabeça da lista.
Nesta abstracção a operação removeMin() é simples, a operação
insertItem(k,e) é mais complexa porque o elemento deve ser inserido na
posição correcta para a fila continuar ser ordenada.
Heap
Uma estrutura não linear, parecida com uma árvore binária.
7
Ordem de grandeza das Chaves

Usamos objectos comparadores especiais
para poder comparar chaves

Objecto comparadore é externo.

Quando a fila com prioridade precisa de
comparar duas chaves, ela usa
comparador que foi fornecido para
comparar este tipo de chaves.

Desta forma a fila com prioridade pode ser
generica e guardar todo tipo de objectos.

TAD Comparator inclui os seguintes
metodos:
-isLessThan(a, b)
-isLessThanOrEqualTo(a,b)
-isEqualTo(a, b)
-isGreaterThan(a,b)
-isGreaterThanOrEqualTo(a,b)
-isComparable(a)
8
Implementação FCP
sequencia não ordenada

Os elementos de S são composição de dois elementos: k
(chave) e e (elemento).

Podemos implementar insertItem() usando insertLast() da
sequencia. O tempo de execução é O(1).

Como inserção é sempre feita no fim, a sequencia não esta
ordenada.
9
Implementação FCP
sequencia não ordenada

Para os metodos minElement(), minKey(), e removeMin(), nos
devemos procurar em todos os elementos da sequencia S. O pior caso
é de O(n).
10
Implementação FCP
sequencia ordenada

Nesta implementação os métodos minElement(), minKey(), e
removeMin() demoram O(1)

A operação insertItem(), no pior caso vai demorar O(n) para
encontrar o lugar de inserção do elemento.
11
Implementação FCP
sequencia ordenada
public class SequenceSimplePriorityQueue implements
SimplePriorityQueue {
protected Sequence seq = new NodeSequence();
protected Comparator comp;
// auxiliary methods
protected Object key (Position pos) {
return ((Item)pos.element()).key();
} // note casting here
protected Object element (Position pos) {
return ((Item)pos.element()).element();
} // casting here too
public SequenceSimplePriorityQueue (Comparator c) {comp = c; }
public int size () {return seq.size(); }
12
Implementação FCP
sequencia ordenada
public void insertItem (Object k, Object e) throws InvalidKeyException {
if (!comp.isComparable(k)) {
throw new InvalidKeyException("The key is not valid");}
else {if (seq.isEmpty()) {
//se sequencia esta vazia, é o primeiro item a ser inserido
seq.insertFirst(new Item(k,e)); }
else { //verifica se pode ser inserido no final
if (comp.isGreaterThan(k,key(seq.last()))) {
seq.insertAfter(seq.last(),new Item(k,e)); }
else { //procurar o citio certo para k
Position curr = seq.first();
while (comp.isGreaterThan(k,key(curr))) {
curr = seq.after(curr);
}
seq.insertBefore(curr,new Item(k,e));
}}}
13
Implementação FCP
sequencia ordenada
public Object minElement () throws
EmptyContainerException {
if (seq.isEmpty())
throw new EmptyContainerException("The priority
queue is empty");
else
return element(seq.first());
}
public boolean isEmpty () {
return seq.isEmpty();
}
14
Selection Sort

Selection Sort é uma variante de Ordenação que utiliza FCP
para ordenar a sequencia. FCP é implementado utilizando
uma sequencia não ordenada.


Fase 1, inserção de item para a fila P (O(1) )
Fase 2, remoção do item de P demora tempo proporcional ao
número de elementos da fila (O(n2))
15
Selection Sort (cont.)

Na fase 2 o tempo de execução é o seguinte: A primeira vez que é
executada a operação removeMinElement demora O(n), a segunda
vez demora O(n-1), etc. A ultima vez demora O(1).

O tempo total na fase 2 é:

Sabemos que:

Logo a complexidade da fase 2 é O(n2).
16
Insertion Sort

Insertion sort é a ordenação que resulta quando utilizamos uma
sequencia ordenada na implementação de uma PriorityQueueSort
17
Insertion Sort(cont.)

A fase 2 é melhorada para O(n).

A fase 1 existe um estrangulamento. A primeira chamada a
insertItem demora O(1), a segunda demora O(2), a última
demora O(n) , o tempo total é O(n2).

Selection sort e insertion sort ambas são de ordem O(n2).

Selection sort executa sempre um número de operações
proporcionais a n2, independentemente da sequencia de
entrada.
O tempo de execução da insertion sort varia do tipo de
sequencia de entrada.

18