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

Aula Prática #13 - Dicionários e Filas de Prioridade
(semana de 24/05 a 29/05)

Conteúdos das teóricas

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

• Slides sobre Árvores: 7 - Árvores Binárias
• Slides sobre Filas de Prioridade: 8 - Filas de Prioridade
• Vídeos das teóricas: (a colocar)

Exercício 1) Dicionários e for-each

Um TAD dicionário (também conhecido como mapa ou array associativo) é uma estrutura de dados que guarda pares (chave,valor), associando a cada chave um determinado valor. Uma implementação possível é precisamente usar uma árvore binária de pesquisa que usa a chave para decidir a posição na árvore (garantindo que só existe uma cópia de cada chave).

1. Código de dicionários
   Faça download do código de dado nas teóricas e compile-o:
   • BSTMap - Dicionário de pares (chave,valor) implementado com árvores binárias de pesquisas (ex. métodos: put, get e keys)
   • Download: BSTMapNode.java | BSTMap.java | TestBSTMap.java

   Espreite o ficheiro BSTMapNode.java para ver como um nó é descrito, e note na assinatura como o tipo K (a chave) tem de ser comparável, mas o tipo V não (o valor).

2. Um primeiro teste.
   Execute a classe de teste dos dicionários: $ java TestBSTMap

   Espreite e acompanhe a implementação do método put da classe BSTMap, muito semelhante ao insert de uma árvore binária de pesquisa normal. Note também a assinatura dos principais métodos e o que fazem (get, put, remove e keys). Veja também como são percorridas as chaves do mapa (que são devolvidas numa lista ligada de Java). De um modo geral, quanto temos algo iterável no Java, podemos usar a sintaxe for-each:

   for (TipoElemento variavel : Sequencia) {
        InstrucoesCiclo
   }
   

   Um exemplo seria algo como:
   Mostrar/Esconder Código de exemplo de for-each

   import java.util.LinkedList;
   import java.util.TreeSet;
   import java.util.Set;
   
   public class TestForEach {
      public static void main(String[] args) {
   
         // Criação de Lista Ligada usando a estrutura de dados do próprio Java
         
         // Exemplo de inicialização usando sintaxe "diamond" (<>). Se não
         // colocarmos o tipo no construtor, o Java consegue inferir qual é
         // olhando para a variável que estamos a inicializar      
         LinkedList<String> list = new LinkedList<>();
   
         // Adicionando algumas strings à lista ligada
         list.addLast("testing");
         list.addLast("just");
         list.addLast("for");
         list.addLast("fun");
   
         // Para percorrer a lista podemos usar um for-each
         for (String s : list)
            System.out.println(s);
   
         // Qualquer TAD iterável pode ser usado com um for each
         // Aqui fica um exemplo com... conjuntos (interface Set)
         // TreeSet implementa um conjunto usando árvores binárias de pesquisa
         Set<Integer> set = new TreeSet<>();
         set.add(42); 
         set.add(24);
         set.add(0);
   
         // Podemos usar int por causa do autounboxing
         for (int i : set)
            System.out.println(i);
      }
   }
   

3. Um pequeno exercício para usar dicionários
   Resolva e submeta o problema [ED172] Contagem de palavras, usando como estrutura de dados base um BSTMap.
   Mostrar/Esconder Dicas
   • Este problema é semelhante a problema resolvido nas aulas teóricas (ver slide 79 do capítulo 7)
   • Crie um dicionario do tipo <String,Integer>
   • Para ler as palavras use os métodos hasNext() (para saber se ainda existem palavras para ler) e next() (para ler a próxima palavra)
   • Para cada palavra lida:
     • Se a palavra ainda não existe no dicionário (usar método get()), então colocá-la no dicionário com valor igual a 1 (usar método put())
     • Se palavra já existe, incrementar o seu valor (usar método get() para ler valor e depois método put() para actualizar o valor)
   • No final é só percorrer a lista de chaves (método keys()) usando um for-each e imprimir os valores. Como é uma árvore binária de pesquisa e o keys é feito inorder, as chaves já vêm por ordem alfabética.

Exercício 2) Filas de Prioridade (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]

1. 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
2. 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.

3. 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 sobre dicionários, experimente resolver novamente o ED172 mas desta vez usando um TAD do próprio Java, o TreeMap.
2. Para consolidar os seus conhecimentos sobre filas de prioridade, experimente resolver novamente o ED215 mas desta vez usando um TAD do próprio Java, a PriorityQueue.
3. Experimente implementar uma MaxHeap, usando como base de codigo a MinHeap.
4. Tentem resolver o desafio desta semana (ONI_TE), que é um problema um pouco mais simples e de aplicação quase directa de uma das estruturas de dados desta aula :)
5. 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":

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