-
Uma fila de prioridades é um tipo abstrato de dados que permite executar as seguintes operações sobre S:
encontrar um elemento máximo de S,
extrair um elemento máximo de S,
inserir um novo número em S,
aumentar o valor de um elemento de S,
diminuir o valor de um elemento de S.
http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/priority.html
-
Complementando o comentario do Carlos Bruno:
A chave de cada objeto determina sua prioridade na fila.
Por isso o MAXIMUM (S) retorna o elemento de S que possui a maior chave.
-
Há uma variante dessa definição em que máximo é substituído por mínimo. Para distinguir uma variante da outra, diremos que a primeira é uma fila de prioridades decrescente (ou de máximo) e a segunda é uma fila de prioridades crescente (ou de mínimo).
Filas de prioridades (crescentes e descrescentes) têm um papel fundamental na implementação eficiente de diversos algoritmos célebres, como o algoritmo Heapsort, o algoritmo de Dijkstra, o algoritmo de Prim, e o algoritmo de Huffman.
-
Podemos definir, uma fila de prioridade como sendo um conjunto de elementos, cada um contendo um campo prioridade, com as seguintes operações:
1. construir uma fila de prioridade para n elementos dados;
2. inserir um novo elemento;
3. remover o maior (ou menor) elemento;
4. substituir o maior por um novo elemento; equivalente a inserir seguido de remoção;
5. modificar a prioridade de um elemento.
A implementação de filas de prioridade pode ser feita com base em árvores binárias parcialmente ordenadas, i.e. um heap, onde:
1. todos os níveis, excepto possivelmente o mais baixo, estão cheios e no nível mais baixo todas as folhas em falta estão à direita das que estão presentes;
2. a prioridade associada a um qualquer nó, é maior ou igual, do que a prioridade associada a qualquer dos nós-folha.
Exemplo:
92
/ \
37 86
/ \ / \
33 12 48 57
/ \ /
25 10 8
Se numerarmos os nós da árvore podemos definir uma condição de heap:
[92, 37, 86, 33, 12, 48, 57, 25, 10, 8]
A função MAXIMUM retornaria, portanto, o elemento de maior chave (92).
http://www.dcc.fc.up.pt/~fds/aulas/EDados/1314/Apontamentos/pqueues.pdf
-
Força Guerreiro!!!!!!