Aula Prática #13 - Filas de Prioridade
(guião extra)
Este pequeno guião extra serve apenas para dar alguma experiência prática no que toca a filas de prioridade. Pode começar por recordar o que foi dado nas teóricas:
Um TAD fila de prioridade mantém uma coleção de elementos mantendo maneira de eficiente de inserir elementos e de retirar o elemento mais prioritário (vamos assumir que o mais prioritário é o menor).
Uma maneira de implementar filas de prioridade com operações eficientes em tempo logarítmico é usar um tipo especial de árvores chamadas de heaps. Numa (min)heap, qualquer nó deve sempre ser menor que os seus filhos (o que significa que o menor de todos está na raíz). Além disso, uma heap é uma árvore completa (todos os níveis cheios, excepto potencialmente o último, com os nós colocados o mais à esquerda possível - o que implica que é equilibrada e tem alura O(log n)) e é tipicamente implementada usando um array (onde o nó na posição i tem como filhos os nós nas posições i*2 e i*2+1) [pode espreitar os slides para relembrar]
Compreendo heaps.
Use a seguinte página para visualizar e interagir um pouco com uma (min)heap, tentando depois prever o que vai acontecer ao inserir e remover:
Execute a classe de teste das filas de prioridade: $ java TestMinHeap, acompanhando a execução dos métodos, e espreitando também o ficheiro MinHeap.java para ver como é implementada a heap de mínimo.
Um problema no Mooshak com filas de prioridade .
Resolva e submeta o problema [ED215] Leilões.
Crie uma classe Person para conter um comprador com nome e preço, e implemente nela o interface Comparable, que compara tendo em conta o preço.
Depois de ler o inteiro N, crie uma MinHeap de... compradores, com capacidade para N elementos do tipo Person
Leia as linhas e:
Se for uma oferta, insera a pessoa na heap
Se for uma venda, remova a melhor oferta da heap (como temos uma heapMin, basta que o compareTo dos comparadores reflita isso) e imprima o nome da pessoa que "saiu" da heap.
Exercícios extra para consolidação de conhecimentos
Para consolidar os seus conhecimentos sobre filas de prioridade, experimente resolver novamente o 215 mas desta vez usando um TAD do próprio Java, a PriorityQueue.
Experimente implementar uma MaxHeap, usando como base de codigo a MinHeap.