Estruturas de Dados 2020/2021 (CC1007) - DCC/FCUP

Aula Prática #14 - Dicionários e Filas de Prioridade
(aula extra)

Exercícios para submissão

Esta aula prática é extra (e opcional) pelo que não tem exercícios a contar para a avaliação. O seu objetivo é dar a hipótese de ter algum contacto prático com filas de prioridade e heaps.

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.
  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. Tentem 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. Revisite o problema [ED098] Triagem de Manchester e volte a submetê-lo mas desta vez usando uma única fila de prioridade (ao invés de uma fila por cada cor).

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)