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