FILAS DE PRIORIDADE - PRIORITY QUEUES

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Fila de Prioridades
(Priority Queues)
Alunos: Adeilson, Andréia, Áquisa e Niete
Fila 
 			A fila é uma estrutura de dados do tipo FIFO: “o primeiro elemento que entra é o primeiro que sai” (first in, first out).
A ideia fundamental da fila é que só podemos inserir um novo elemento no final da fila e só podemos retirar o elemento no início.
A estrutura fila é uma analogia natural com o conceito de fila que usamos no nosso dia a dia: quem primeiro entra numa fila é o primeiro a ser atendido (a sair da fila).
É uma fila onde cada elemento possui uma prioridade.
Essa prioridade determina a posição de um elemento na fila, portanto determina quem deve ser o primeiro a ser removido da fila.
Os objetos na fila têm um número indicativo da sua prioridade.
Procurar o próximo objeto a tratar: encontrar o mínimo da fila.
Retirar o objeto a tratar na fila: apagar o mínimo.
Fila de Prioridades
Fila de Prioridades
Tipos de implementações 
Lista encadeada
Heap binária
Array desordenado
Array ordenado
			A escolha do tipo de implementação depende da aplicação, cada tipo de implementação possui um custo diferente em relações as operações (inserção, remoção).
Vantagens e Desvantagens:
			A vantagem de uma fila de prioridade sobre a fila normal é que alguns dados são mais importantes do que outros e por isso podem ser priorizados. A fila de prioridade garante que os objetos mais importantes sejam recuperados em primeiro lugar. No entanto, isso pode significar que os objetos de baixa prioridade sejam esquecidos na fila, nunca sendo removidos. Isto é especialmente verdadeiro se o esquema de atribuição de prioridades tem muitos níveis de prioridade diferentes.
Fila de Prioridades
Onde posso aplicar?
Filas de espera em geral (p. ex. transplantes);
Escalonamento de processos (agendador de tarefas);
Ordenação.
Fila de Prioridades
Lógica
Fila de Prioridades
Construindo uma fila de prioridades
Inserindo o Mário com prioridade 2.
2
Lógica
Fila de Prioridades
Construindo uma fila de prioridades
Inserindo o Quico com prioridade 1.
O Quico foi para o início da fila porque sua prioridade é maior.
2
1
Lógica
Fila de Prioridades
Construindo uma fila de prioridades
Inserindo Michael Jackson com prioridade 4
2
1
4
Lógica
Fila de Prioridades
Construindo uma fila de prioridades
Inserindo o Batman com prioridade 3.
2
1
4
3
Fila de Prioridades
Algoritmo
Fila de Prioridades
Execução