Implementacao de Fila de Prioridades e Analise do Algoritmo de Prim

2 Uma fila de prioridades é uma fila na qual o elementos são processados de acordo com suas prioridades As operações mais comuns de uma fila de prioridades são INSERIRFILAQep operação que insere um elemento e com prioridade p em uma fila de prioridades Q EXTRAIRMINFILAQ operação que extrai e retorna o elemento de menor prioridade da fila Q EHVAZIAQ operação que retorna Verdadeiro se a fila Q é vazia e Falso caso contrário ATUALIZAPRIORIDADEFILAQup operação que atualiza a prioridade do elemento u para p na fila de prioridade Q Fila de prioridade é um tipo abstrato de dados e por conseguinte pode ser implementado de diversas formas a Escreva o pseudocódigo de uma implementação de filas de prioridades usando vetores e analise o tempo de execução do seu código b Escreva o pseudocódigo de uma implementação de filas de prioridades usando heap binária e analise o tempo de execução do seu código c Assumindo que a estrutura lista de adjacências foi utilizada para representar o grafo e que vetores foram utilizados para representar a fila de prioridades analise o tempo de execução do Algoritmo 1 d Assumindo que a estrutura lista de adjacências foi utilizada para representar o grafo e que uma heap binária foi utilizada para representar a fila de prioridades analise o tempo de execução do Algoritmo 1 e Assumindo que a estrutura matriz de adjacências foi utilizada para representar o grafo e que vetores foram utilizados para representar a fila de prioridades analise o tempo de execução do Algoritmo 1 f Assumindo que a estrutura matriz de adjacências foi utilizada para representar o grafo e que uma heap binária foi utilizada para representar a fila de prioridades analise o tempo de execução do Algoritmo 1 Algorithm 1 Algoritmo de Prim 1 Função PRIMGw w EG ℝ é uma função que dá custo às arestas Qual estrutura de dados você usará para representar isso 2 Cria uma fila de prioridades Q 3 Para cada u VG faça 4 INSERIRFILAQu 5 predu Null 6 Seja s VG 7 preds s 8 keys 0 9 Enquanto EHVAZIAQ faça 10 u ExtrairMinFilaQ 11 Para cada v Nu faça 12 Se v Q e wuv keyv então 13 predv u 14 ATUALIZAPRIORIDADEFILAQvwuv EXERCÍCIO PSEUDOCÓDIGO ALGORITMO DE PRIM b FILADEPRIORIDADES array heap int tamanho CONSTRUTOR heap novo array tamanho 0 INSERIRFILAQ e p Qheaptamanho e p Qtamanho Qtamanho 1 i Qtamanho 1 enquanto i 0 e QheapPAIiprioridade Qheapiprioridade TROCARQheapi QheapPAIi i PAIi EXTRAIRMINFILAQ se QEHVAZIA retornar nulo minimo Qheap0 Qtamanho Qtamanho 1 Qheap0 QheapQtamanho MINHEAPIFYQ 0 retornar minimo EHVAZIAQ retornar Qtamanho 0 ATUALIZAPRIORIDADEFILAQ u p para i 0 até Qtamanho 1 se Qheapielemento u prioridadeAntiga Qheapiprioridade Qheapiprioridade p se p prioridadeAntiga enquanto i 0 e QheapPAIiprioridade Qheapiprioridade TROCARQheapi QheapPAIi i PAIi senão MINHEAPIFYQ i quebrar PAIi retornar chãoi 1 2 ESQUERDAi retornar 2 i 1 DIREITAi retornar 2 i 2 EXERCÍCIO PSEUDOCÓDIGO ALGORITMO DE PRIM MINHEAPIFYQ i l ESQUERDAi r DIREITAi se l tamanho e Qheaplprioridade Qheapiprioridade menor l senão menor i se r tamanho e Qheaprprioridade Qheapmenorprioridade menor r se menor i TROCARQheapi Qheapmenor MINHEAPIFYQ menor TROCARa b temp a a b b temp Análise de tempo A complexidade de tempo da operação INSERIRFILA é Olog n porque envolve mover o elemento para cima do heap até que ele alcance sua posição correta A complexidade de tempo da operação EXTRAIRMINFILA também é Olog n porque envolve mover o último elemento do heap para a raiz e depois movêlo para baixo do heap até que ele alcance sua posição correta A complexidade de tempo da operação EHVAZIA é O1 porque envolve apenas verificar o tamanho do heap A complexidade de tempo da operação ATUALIZAPRIORIDADEFILA é On no pior caso porque envolve procurar o elemento no heap e depois movêlo para cima ou para baixo do heap até que ele alcance sua posição correta d Análise de tempo Assumindo que uma lista de adjacências é usada para representar o grafo e que uma heap binária é usada para representar a fila de prioridades o tempo de execução do Algoritmo 1 é OVElogV onde V é o número de vértices e E é o número de arestas do grafo A operação INSERIRFILA leva tempo OlogV e é executada V vezes resultando em um tempo total de OVlogV A operação EXTRAIRMINFILA também leva tempo OlogV e é executada V vezes resultando em um tempo total de OVlogV A operação ATUALIZAPRIORIDADEFILA leva tempo OlogV e é executada no máximo E vezes resultando em um tempo total de OElogV Portanto o tempo total de execução do algoritmo é OVElogV EXERCÍCIO PSEUDOCÓDIGO ALGORITMO DE PRIM e Análise de tempo Se a estrutura matriz de adjacências foi utilizada para representar o grafo e vetores foram utilizados para representar a fila de prioridades o tempo de execução do Algoritmo 1 seria OV² onde V é o número de vértices do grafo Isso ocorre porque a operação EXTRAIRMINFILAQ leva tempo OV e é executada V vezes enquanto as outras operações levam tempo constante No entanto se outras estruturas de dados forem utilizadas para implementar a fila de prioridades como um heap binário o tempo de execução pode ser reduzido para OE log V onde E é o número de arestas do grafo A função w que dá custo às arestas pode ser representada por um vetor ou um mapa onde cada índice ou chave representa uma aresta e o valor armazenado é o custo da aresta Essa estrutura de dados deve permitir acesso rápido aos custos das arestas para que o algoritmo possa ser executado eficientemente f Análise de tempo Ao assumir que a estrutura matriz de adjacências foi utilizada para representar o grafo e que uma heap binária foi utilizada para representar a fila de prioridades podemos analisar o tempo de execução do Algoritmo 1 Algoritmo de Prim da seguinte maneira A operação INSERIRFILAQ u é executada para cada vértice do grafo ou seja V vezes Como a inserção em uma heap binária tem complexidade OlogV o tempo total para essa parte do algoritmo é OVlogV A operação EXTRAIRMINFILAQ é executada enquanto a fila não estiver vazia ou seja V vezes Como a extração do mínimo em uma heap binária tem complexidade OlogV o tempo total para essa parte do algoritmo é OVlogV A operação ATUALIZAPRIORIDADEFILAQ v wuv é executada para cada aresta do grafo ou seja E vezes Como a atualização da prioridade em uma heap binária tem complexidade OlogV o tempo total para essa parte do algoritmo é OElogV Como a matriz de adjacências foi utilizada para representar o grafo verificar se um vértice v está na fila Q v Q tem complexidade O1 Portanto o tempo total de execução do Algoritmo 1 Algoritmo de Prim nesse caso é OVlogV ElogV