Fila de Prioridades
UnB-\(\gamma\)

1. Introdução

2. Exercícios

1. Resolva os exercícios de PQ   prof_Feofiloff
   
   • https://www.ime.usp.br/~pf/estruturas-de-dados/aulas/priority.html
2. (SW 9.1) Suponha que a sequência P R I O * R * * I * T * Y * * * Q U E * * * U * E é aplicada a uma PQ de máximo inicialmente vazia. Uma letra significa inserção e um asterisco significa remoção do máximo. Dê a sequência de letras produzida pelas remoções.   Sedgewick
   
3. (SW 9.17) Um vetor em ordem decrescente é um heap decrescente? Um vetor em ordem crescente é um heap crescente?   Sedgewick
   
4. Insira os itens E A S Y Q U E S T I O N, nessa ordem, em um heap decrescente inicialmente vazio. Mostre o heap que resulta.   Sedgewick
   
5. Escreva um método isMaxHeap() para verificar se o vetor pq[] é um heap decrescente. O seu algoritmo deve consumir tempo linear. Repita para heap crescente.   Sedgewick
   
6. Fila priorizada min/max. Projete um tipo-de-dados que dê suporte às seguinte operações: inserção, remoção do mínimo, remoção do máximo, encontrar o mínimo (sem remover), e encontrar o máximo (sem remover). As três primeiras operações devem consumir tempo logarítmico e as duas últimas devem consumir tempo constante. Dica: Use dois heaps.   Sedgewick
   
7. Escreva a API completa de Filas de Prioridade de maneira que ela suporte mais de um Fila de prioridades no seu programa
   
8. Como você pode implementar um algoritmo de Ordenação utilizando o conceito de filas de prioridade?
   
   • Analise e entenda a implementação simples usando fila de prioridades AQUI
   • Pense em como modificar o algoritmo acima para não utilizar memória auxiliar, uma solução está AQUI
9. Rode o conjunto de benchmark de ordenação e idenfique o comportamento dos algoritmos HeapSort e PQsortsimple quando se comparado com o melhor quicksort e o mergesort
   
10. O HeapSort é estável?
    
11. Você é capaz de ressolver esta ISSUE?
    
12. Qual implementação (em vetor ordenado ou não ordenado, com lista encadeada ordenada ou não ordenada, árvore binária em vetor) para encontrar os \(100\) menores elementos de um conjundo de \(10^6\) números aleatórios?   Sedgewick
    
    • Implemente e faça testes de desempenho
13. Resolva o problema Classificados de Sementes utilizando os conceitos de fila de prioridades
    
    • Você pode ler o Enunciado aqui
    • O exercício pode ser resolvido na lista de exercícios de Quicksort
14. É possível resolver o problema kk-página utilizando os conceitos de fila de prioridades?
    
    • Você pode ler o Enunciado aqui
    • O exercício pode ser resolvido na lista de exercícios de Quicksort
15. Resolva o problema Eu posso advinhar a estrutura de dados!   urionlinejudge
    
16. Implemente a ADT de fila de prioridades para fazer a troca baseada em índice (como vimos no fim da última aula)
    

17. Suponha que um vetor está preenchido com as seguintes chaves E A S Y Q U E S T I O N. Imprima o conteúdo do vetor pq e qp após a inserção dos elementos da fila de prioridades implementada no exercício 2.0.0.16
    
18. Adicione a operação remover na sua implementação do problema 2.0.0.16
    
    • esta função serve para quando se remover um elemento qualquer do vetor original
19. Resolva o exercício Churrascarias da Avenida utilizando a implementação feita no exercício 2.0.0.16   spoj br
    

3. Vídeos Adicionais