Estruturas de Dados 2022/2023 (CC1007) - DCC/FCUP

Aula Prática #12 - Filas de Prioridade (e revisões)
(12/12 a 16/12)

Esta aula prática é um pouco mais pequena, para lhe dar mais tempo para "respirar" e por ser a última antes do final das aulas :)

Exercícios para submissão

Para efeitos da nota atribuída à resolução de exercícios ao longo do semestre, os exercícios que pode submeter desta aula são:

• [ED215] Leilões (peso 100%) (exercício do guião principal)
• [ED259] Turismo Espacial (peso 100%) (exercício de desafio)

Prazo de submissão: 30 de dezembro (submeter no Mooshak de EDados)

É encorajado que vão falando com os docentes e outros colegas se tiverem dificuldades. No entanto, qualquer ajuda mais direta que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem.
Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota.
Cada aula vale 11% da nota desta componente. Como existem 11 aulas com submissões, pode ter pontuação máxima mesmo sem ter feito tudo.
Para um problema contar tem acertar todos os testes (ou seja, ter accepted). Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.
Para ter 100% bastará sempre resolver os exercícios do guião principal.

Conteúdos das teóricas

Nesta aula iremos abordar conceitos de Filas de Prioridade. Será por isso conveniente ver o que foi falado nas teóricas:

• Slides sobre Fila de Prioridade: 8 - Árvores Binárias
• Vídeos das teóricas: #24 - Filas de Prioridade e Heaps

Exercício 1) Compreendendo Filas de Prioridade e Heaps

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:
  • Visualização de heaps
• Código de heaps.
  Faça download do código de dado nas teóricas e compile-o:
  • MinHeap - Fila de prioridade com MinHeap (ex. métodos: insert, min, removeMin)
  • Download: MinHeap.java | TestMinHeap.java

  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.

Descobrindo o mínimo e o máximo.
Exercício 2) Submtendo um problema

• Um problema no Mooshak com filas de prioridade .
  Resolva e submeta o problema [ED215] Leilões (disponível no volume de árvores).
  Mostrar/Esconder Dicas
  • 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

1. Para consolidar os seus conhecimentos, experimente resolver novamente o ED215 mas desta vez usando um TAD do próprio Java, a PriorityQueue.
2. Experimente implementar uma MaxHeap, usando como base de codigo a MinHeap.
3. Tente resolver o desafio desta semana (ED259), que é um problema um pouco mais simples que o habitual para um desafio e de aplicação quase directa de filas de prioridade :)
4. Preparação para o teste #2: se ainda não o fez, pode e deve espreitar e tentar fazer os exercícios extra de revisão/preparação para esse segundo teste prático.

Exercício de Desafio

Para esta semana vou colocar um exercício da minha autoria que envolve uma das estruturas de dados que foi falada nesta aula e que que foi usado nas Olimpíadas de Informática "há muito muito tempo":

• [ED259] Turismo Espacial (Final Nacional das Olimpíadas Nacionais de Informática'2007)