Fila de Prioridade: Estruturas de Dados e Aplicações

Fila de Prioridade Listas Filas e Pilhas Vimos até agora várias Estrutura de Dados ED lineares como Listas Filas e Pilhas Cada uma destas ED possuíam ou não restrições em relação às operações que podiam executar Listas inserção e remoção sem restrições Filas apenas inserção no final e remoção no início da estrutura FIFO Pilhas apenas inserção no final e remoção no final LIFO Na maior parte das operações destas ED os seus elementos eram tratados de forma igual Ou seja os elementos possuíam a mesma importância Em muitas aplicações uma característica importante que distingue os dados em uma determinada estrutura é uma prioridade atribuída a cada um deles Fila de Prioridade Priority Queues ATENDIMENTO PREFERENCIAL Heap Exemplo 95 60 78 39 28 66 70 33 Fila de Prioridades Priority Queue Fila de Prioridade ou Lista de Prioridade é uma ED que armazena uma coleção de dados de elementos priorizados ou seja cada um dos seus elementos possui um prioridade associada A importância ou prioridade do elemento é determinada pela sua chave Chave do elemento A prioridade pode ser um dado adicional definido por um valor numérico ou algum atributo já existente do próprio elemento Em uma Fila de Prioridade um elemento com prioridade maior deve ser atendido antes que os elementos de prioridade menor Caso dois ou mais elementos possuam uma mesma prioridade a ordem de atendimento normalmente é definida pela ordem de chegada como uma fila comum ou pode não ser definida depende da aplicação Fila de Prioridade Exemplos Lista de tarefas que um funcionário deve realizar durante o dia Algumas tarefas a mais prioritárias são mais importantes e devem ser executadas antes as de menor prioridade Em filas de banco ou supermercado existe um esquema de prioridade para alguns tipos de clientes como idosos e grávidas que devem ser atendidos primeiros Uma fila de pacientes esperando por um transplante de fígado é normalmente uma Fila de Prioridade Fila de Prioridade Aplicações As Filas de prioridades desempenham um papel de grande importância em diversos algoritmos consagrados na computação Algoritmos de ordenação Heapsort Algoritmos de roteamento em mapas Algoritmo de Dijkstra e Algoritmo A Encontrar os melhores caminhos para implantar cabos de fibra óptica para ligar os blocos de uma Universidade Algoritmo de Prim Compactação de arquivos Algoritmo de Huffman TAD Fila de Prioridade Filas de Prioridade como quaisquer outros TADs requerem a definição de operações que são realizadas sobre elas como FilaPrioridade Cria uma nova Fila de Prioridade inseree ou inseree p insere um elemento e com prioridade p na Fila de Prioridade a prioridade também pode ser um campo dentro do próprio e remove remove e retorna o elemento de maior prioridade espia ou consulta retorna sem remover o elemento de maior prioridade estaVazia retorna um booleano indicando se a Fila de P está vazia ou não estaCheia retorna um booleano indicando se a Fila de P está cheia ou não tamanho retorna o número de elementos da Fila de P imprime imprime a Fila Fila de Prioridade Implementações As Filas de Prioridade podem ser implementadas usando algumas abordagens Por uma lista não ordenada Por uma lista ordenada Por uma Heap A diferença destas abordagens de implementação está no desempenho dos principais métodos das Filas de Prioridade ou seja insere remove e espia Também podemos implementar as Filas de Prioridade utilizado estruturas Estáticas utilizase vetor Dinâmica utilizase uma estrutura encadeada através de referências Fila de Prioridade Por Lista não Ordenada Na inserção podese colocar o novo elemento em qualquer posição conveniente da lista tempo constante Na remoção e na consulta é necessário percorrer todos os elementos da estrutura para buscar aquele de maior prioridade tempo proporcional a n Na remoção é preciso estabelecer uma regra de comparação entre os elementos com o objetivo de indicar qual o elemento possui maior prioridade Chave sendo uma prioridade explícita objeto Tarefa nome tempo prioridade Chave sendo um atributo do elemento objeto Jogador de Basquete nome idade altura Prioridade dada pela altura do jogador Chave pode ser o próprio elemento Fila de Prioridade de Inteiros Fila de Prioridade Por Lista não Ordenada A tabela abaixo mostra um exemplo de uma série de operações sobre uma Fila de Prioridade P inicialmente vazia de elementos inteiros Assuma a chave com o próprio valor inteiro e a inserção ocorre no final de P Operação Retorno Início P Final Operação Retorno Início P Final 0 estaVazia true 6 insere5 3 8 5 1 insere7 7 7 espia 8 3 8 5 2 insere3 7 3 8 contem3 true 3 8 5 3 remove 7 3 9 tamanho 3 3 8 5 4 insere8 3 8 10 remove 8 3 5 Fila de Prioridade Por Lista Ordenada Na inserção é necessário colocar o novo elemento na posição que deixe os elementos ordenados tempo proporcional a n Na remoção e na consulta basta remover o primeiro elemento caso lista ordenada decrescente ou o último elemento caso lista ordenada crescente tempo constante É preciso estabelecer uma regra de comparação entre os elementos com o objetivo de indicar qual o elemento possui maior prioridade Fila de Prioridade Por Lista Ordenada A tabela abaixo mostra um exemplo de uma série de operações sobre uma Fila de Prioridade P inicialmente vazia de elementos inteiros Assuma a chave com o próprio valor inteiro e a ordenação crescente remove final Operação Retorno Início P Final Operação Retorno Início P Final 0 estaVazia true 6 insere5 3 5 8 1 insere7 7 7 espia 8 3 5 8 2 insere3 3 7 8 contem7 false 3 5 8 3 remove 7 3 9 tamanho 3 3 5 8 4 insere8 3 8 10 remove 8 3 5 Fila de Prioridade Por Heap As duas implementações apresentadas até agora tinham algumas inconveniências de desempenho em relação aos métodos ou de inserção ou remoção Listas não ordenadas inserção era bem mais eficiente do que a remoção Lista ordenadas remoção era bem mais eficiente do que a inserção Com o objetivo de aplicar uma abordagem mais eficiente considerando tanto a inserção quanto a remoção será utilizado as estruturas Heaps Não confundir a estrutura de dados Heap com a área de memória Heap alocação dinâmica de variáveis Fila de Prioridade Por Heap A implementação eficiente de uma Fila de Prioridade utiliza uma Estrutura de Dados chamada de Heap Usando Heaps o tempo de execução dos métodos de inserçãoremoção deixam de ser proporcionais a n e passam a ser proporcional ao logaritmo de n A forma como a implementação via Heap obtém este avanço na eficiência dos métodos está na ideia de abandonar uma navegação linear dentro da estrutura Em vez disso uma abordagem hierárquica é aplicada Árvore Heap A Heap é uma Estrutura de Dados que pode ser representada de forma linear utilizando um vetor mas a melhor visualização é feita como uma árvore completa heap binária Árvore nós raíz folhas paifilhos ligações Binária no máximo dois filhos Completa a árvore está preenchida em todos os níveis exceto possivelmente no nível mais baixo Na visualização em árvore os nós são numerados sequencialmente da raíz para os níveis mais baixos da esquerda para a direita Heap Estas ED podem ser Heaps de Máximo ou Heaps de Mínimo As Heaps de Máximo devem cumprir a seguinte propriedade cada nó possui prioridade maior que seus dois filhos se existirem Elemento de maior prioridade é a raíz As Heaps de Mínimo seguem o comportamento oposto Desta forma utilizamse normalmente as Heaps de Máximo na implementação de Filas de Prioridades Heap Como a estrutura de árvore está implícita no vetor Assumindo um vetor V1n contagem começa de 1 A raiz da árvore é V1 Dado o índice i de um nó podemos calcular os índices de seu pai i2 do filho à esquerda 2i e do filho à direita 2i 1 Um elemento raiz não tem pai Um elemento i só tem filho esquerdo se 2i n e só tem filho direito se 2i1 n i 2i 2i 1 Fila de Prioridade Por Heap Inserção A inserção em uma Fila de Prioridade via Heap é necessário seguir os seguintes passos Coloque o novo elemento no final da Heap incrementando o número de elementos Esta operação pode deixar a Heap desordenada ou seja a propriedade da Heap não ser satisfeita Subiremos o novo elemento em direção à raiz da árvore trocando ele pelo seu pai A troca só será necessária caso o pai seja menor que o nó em questão filho Quando o filho se tornar menor que o pai ou alcançarmos a raiz paramos a subida Neste caso a Heap voltou a estar ordenada O tempo de inserção é proporcional a log2n Fila de Prioridade Por Heap Inserção 8 6 7 4 2 4 2 6 7 8 9 6 8 4 2 7 4 2 7 6 8 9 8 6 7 4 2 9 4 2 9 6 7 8 8 6 9 4 2 7 4 2 7 6 9 8 Lembremse da propriedade em uma heap de máximo VPaii Vi ou Vi2 Vi Fila de Prioridade Por Heap Remoção A remoção em uma Fila de Prioridade via Heap é necessário seguir os seguintes passos Armazene o elemento a ser removido No caso este é o elemento de maior prioridade e estará localizado na raiz V1 Troque o elemento raiz pelo o último elemento da estrutura Em seguida decremente o número de elementos da Heap Essa operação tornará a Heap desordenada Descemos o elemento localizado na raiz em direção aos nó folhas da árvore trocando ele pelo filho de maior prioridade caso seja necessário Esta troca só será necessária caso o pai seja menor que o filho Quando o pai se tornar maior que os filhos ou alcançar uma folha paramos a descida Neste caso a Heap voltou a estar ordenada O tempo de remoção é proporcional a log2n Fila de Prioridade Por Heap Remoção 9 7 6 4 5 3 4 5 3 7 6 9 7 5 6 4 3 9 4 3 9 5 6 7 3 7 6 4 5 9 4 5 9 7 6 3 7 3 6 4 5 9 4 5 9 3 6 7 Atenção no última figura da remoção o elemento 9 não faz parte da Heap Desta forma ele está dentro da área hachurada apenas para indicar que os elementos válidos são os 5 primeiros Fila de Prioridade Por Heap Nos métodos de inserção e remoção utilizamos um artifício de Subir ou Descer um determinado elemento dentro da Heap Subir e Descer devem ser na verdade métodos de uma Heap que irá rearranjar a estrutura de modo que a propriedade da Heap se mantenha O Descer Heapfy resolve o problema de colocar um elemento na posição correta da Heap deslocando este elemento para baixo usado na remoção Para este método funcionar a subárvore à direita e à esquerda devem ser uma heap O Subir desloca o elemento que fere a propriedade da Heap para cima usado na inserção Para isso todos os ancestrais do elemento que irá subir devem ser uma Heap Fila de Prioridade Por Heap A tabela abaixo mostra um exemplo de uma série de operações sobre uma Fila de Prioridade P inicialmente vazia de elementos inteiros implementada via Heap Assuma a chave com o próprio valor inteiro e uma Heap de Máximo Operação Retorno Início P Final Operação Retorno Início P Final 0 estaVazia true 6 insere5 8 3 5 1 insere7 7 7 espia 8 8 3 5 2 insere3 7 3 8 contem7 false 8 3 5 3 remove 7 3 9 tamanho 3 3 5 8 4 insere8 8 3 10 remove 8 5 3