Estruturas de Dados 2004/2005
25
Filas Prioritárias - Priority Queue
* TAD que permite que o item com maior valor de chave (maior prioridade) seja
facilmente acedido e removido da estrutura.
* Existe uma função que, a cada novo item, associa uma prioridade para inserção na PQ e
que determinará a sua saı́da (em função das restantes prioridade)
Filas Prioritárias - Operadores Mı́nimos
• criarPQ() – cria uma PQ vazia;
• vaziaPQ(P) – devolve V sse p é vazia;
• inserePQ(x, P) – insere x em P de acordo com a sua prioridade;
• consultaPQ(P) – devolve o item com a maior prioridade em P;
• removePQ(P) – retira e devolve o nó com a maior prioridade em P;
Estruturas de Dados 2004/2005
Filas Prioritárias - Representações possı́veis
• Representação Estática:
tabela unidimensional ordenada;
• Representações Dinâmicas:
– Lista Ligada Ordenada;
– Árvore Binária;
Numa Árvore Binária de Pesquisa:
• o item com o maior valor de chave (prioridade) encontra-se na sub–árvore mais à direita
• o item com o menor valor de chave (prioridade) encontra-se na sub–árvore mais à
esquerda
26
Estruturas de Dados 2004/2005
27
Árvore Binária Completa: árvore binária de altura h onde:
– todos os nós até à altura h − 2 têm 2 filhos
– se um nó do nı́vel h − 1 tem um descendente direito, todos os seus descendentes
esquerdos que são folhas estão no nı́vel h
Filas Prioritárias - Heap
• Árvore binária completa
• Relação de ordem: todos os descendentes de um nó têm prioridade mais baixa do que
esse nó
• cada sub–árvore é uma heap
Se pudermos estimar com segurança, o número máximo de elementos para a Fila Prioritária,
pudemos usar uma estrutura de Tabela Unidimensional
Estruturas de Dados 2004/2005
28
Filas Prioritárias em Heap – Remoção
Numa heap, o valor a remover (de maior prioridade) está na raiz da árvore
. devolver valor (nó) na raiz;
. copiar para o nó raiz o valor do último nó da árvore e remover este;
. “re-ordenar” árvore: seja R a raiz
– se o nó é folha ou se tem maior prioridade que os seus filhos: voltar;
– caso contrário: seja J o filho com maior prioridade
∗ trocar( raiz R filho J )
∗ “re-ordenar” sub–árvore J:
Numa heap, o “reordenamento”devido a remoção é, no pior dos casos, da O(log 2 n)
Estruturas de Dados 2004/2005
29
Filas Prioritárias em Heap – Inserção
. inserir novo nó na última posição livre na árvore;
. enquanto não atingir a raiz e pai do nó actual for de menor prioridade:
– trocar pai com nó actual;
– actualizar nó actual para o seu avô;
Numa heap, o “reordenamento” devido a inserção é, no pior dos casos, da O(log 2 n)