Filas priorizadas

Livro de Sedgewick e Wayne: parte da sec.2.4, p.308.  Website do livro: resumo sec.2.4, slides.  Código fonte, documentação, e dados de teste de todos os programas do livro: veja algs4.cs.​princeton.edu/​code/.

Uma fila priorizada (ou fila com prioridades) é um ADT (abstract data type) que generaliza tanto a fila quanto a pilha.

Introdução

• Filas priorizadas (priority queues, ou PQs) são ADTs que manipulam conjuntos de coisas comparáveis que chamaremos itens.
• Um item k é máximo se nenhum item é estritamente maior que k e mínimo se nenhum item é estritamente menor que k.  Podemos ter mais de um item máximo e mais de um item mínimo.
• Uma fila priorizada decrescente ou PQ de máximo é um ADT que manipula um conjunto de itens por meio de duas operações fundamentais:
  • inserção de um novo item no conjunto e
  • remoção de um item máximo.
• Uma fila priorizada crescente ou PQ de mínimo é definida de maneira análoga.
• Eis a API que especifica as operações de uma PQ de máximo (algumas operações auxiliares foram acrescentadas às duas fundamentais):

  public class MaxPQ<Item extends Comparable<Item>>
  	MaxPQ()	cria uma PQ de máximo
  	MaxPQ(int cap)	cria uma PQ de máximo com capacidade cap
  	MaxPQ(Item[] a)	cria uma PQ de máximo com os itens que estão em a[]
  void	insert(Item v)	insere o item v nesta PQ
  Item	max()	devolve um item máximo deste PQ
  Item	delMax()	remove e devolve um item máximo desta PQ
  boolean	isEmpty()	esta PQ está vazia?
  int	size()	número de itens desta PQ

• [O livro diz Key onde em digo Item. Acho que minha terminologia é mais adequada.]
• A expressão  Item extends Comparable<Item>  na definição da API indica que o tipo genérico Item deve satisfazer a interface Comparable, ou seja, deve ter um método compareTo() para comprar objetos do tipo Item.  (Esse é o caso, por exemplo, dos tipos referência Integer, Double e String, mas não é o caso dos tipos primitivos int e double.)  (A propósito, por que extends?  Não deveria ser Item implements Comparable<Item>?  Não. As razões são técnicas e um tanto complexas. Veja artigo no StackOverflow.)
• A API de uma PQ de mínimo é análoga: basta trocar max por min.

Exercícios 1

1. Critique a seaguinte definição alternativa de máximo:  um item é máximo se for maior que todos os outros.
2. Por que uma fila é um caso especial de PQ?  Por que uma pilha é um caso especial de PQ? 

Exemplo de cliente de fila priorizada

• Imagine uma empresa de cartões de crédito que tem uma classe Transaction de objetos que representam as compras feitas por seus clientes. Cada objeto da classe contém o nome de um cliente, a data de uma transação, e o valor da transação.  As transações são comparadas pelo seu valor.

  public class Transaction implements Comparable<Transaction> {
  
     private final String name;
     private final String date;
     private final double value;
  
     // Construtor. Cria uma transação a partir da string tr.
     Transaction(String tr) {
        . . . 
     }
  
     // Compara esta transação com a transação that.
     public int compareTo(Transaction that) {
        if (this.value > that.value) return +1;
        if (this.value < that.value) return -1;
        return 0;
     }
  }
  

• No código do método compareTo() acima, a palavra reservada this serve para resolver a ambiguidade em torno das variáveis value. Assim, this.value é a variável value da classe Transaction que estamos definindo, enquanto that.value é a variável value da do objeto that que é parâmetro do método compareTo().
• Exemplo: Cada linha do seguinte arquivo pode ser usada para criar um objeto Transaction:

  % more tinyBatch.txt
  Turing       17/6/1990   644.08
  vonNeumann   26/3/2002  4121.85
  Dijkstra     22/8/2007  2678.40
  vonNeumann   11/1/1999  4409.74
  Dijkstra    18/11/1995   837.42
  Hoare        10/5/1993  3229.27
  vonNeumann   12/2/1994  4732.35
  Hoare        18/8/1992  4381.21
  Turing       11/1/2002    66.10
  Thompson     27/2/2000  4747.08
  Turing       11/2/1991  2156.86
  Hoare        12/8/2003  1025.70
  vonNeumann  13/10/1993  2520.97
  Dijkstra     10/9/2000   708.95
  Turing      12/10/1993  3532.36
  Hoare        10/2/2005  4121.85
  

• Problema: Dada uma enorme lista de transações e um número M, imprimir as M transações de maior valor.  (A lista é tão grande que não cabe na memória rápida. Para tornar o problema mais difícil, suponha também que M é grande.)
• O programa TopM recebe a lista de transações (uma transação por linha) e imprime as M transações de maior valor, em ordem decrescente.  O programa usa uma fila priorizada MinPQ cujos itens são transações:

  public class TopM {
  
     public static void main(String[] args) { 
        int M = Integer.parseInt(args[0]);
  
        MinPQ<Transaction> pq = new MinPQ<Transaction>(M + 1);
  
        while (StdIn.hasNextLine()) { 
           pq.insert(new Transaction(StdIn.readLine()));
           if (pq.size() > M)
              pq.delMin(); 
        }
        // As M maiores transações estão na pq.
  
        Stack<Transaction> stack = new Stack<Transaction>();
        while (!pq.isEmpty()) 
           stack.push(pq.delMin());
        for (Transaction t : stack)  // foreach
           StdOut.println(t);
     }
  }
  

• Exemplo de execução:

  % java TopM 5 < tinyBatch.txt
  Thompson    27/2/2000  4747.08
  vonNeumann  12/2/1994  4732.35
  vonNeumann  11/1/1999  4409.74
  Hoare       18/8/1992  4381.21
  vonNeumann  26/3/2002  4121.85
  

Implementações elementares

• É fácil escrever uma implementação de MinPQ armazenando os itens em um vetor ou lista ligada.
• Se o vetor ou lista forem mantidos em ordem, delMin() é rápido mas insert() é lento:  s temos N itens, delMin() consome tempo constante e insert() consome tempo proporcional a N.
• Se o vetor ou lista não estiverem em ordem, insert() é rápido mas delMin() é lento:  se temos N itens, insert() consome tempo constante e delMin() consome tempo proporcional a N.
• Algo análogo vale para MaxPQ.

Exercícios 2

1. (SW 2.4.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.

Implementação rápida, baseada em heap

• Um heap é um tipo de árvore binária inventado para implementar fila priorizada eficientemente.
• Há dois sabores de heaps:  decrescente (o máximo fica no topo) e crescente (o mínimo fica no topo).
• Propriedade que define um heap decrescente:  o item de qualquer nó é menor ou igual que o item do seu pai.  Propriedade que define um heap crescente: o item de qualquer nó é maior ou igual que o item do seu pai.
• Exemplo de heap decrescente (os itens são strings com 1 caractere cada):

  

• Representação de um heap em um vetor a[1..N]:  os dois filhos do índice k são  2*k  e  2*k+1.  Reciprocamente, o pai de qualquer índice k é  ⌊k/2⌋.

  

• Exemplo: Conserta de-baixo-para-cima (swim) um defeito num heap decrescente:

  

• Exemplo: Conserta de-cima-para-baixo (sink) um defeito num heap decrescente:

  

• Algoritmo 2.6:  PQ de máximo implementada em um heap decrescente:

  public class MaxPQ<Item extends Comparable<Item>> {
  
     private Item[] pq; 
     private int N = 0; // heap fica em pq[1..N]
  
     public MaxPQ(int maxN) { // construtor
        pq = (Item[]) new Comparable[maxN+1]; 
     }
  
     public boolean isEmpty() {
        return N == 0;
     }
     
     public int size() {
        return N;
     }
  
     public void insert(Item v) {
        pq[++N] = v;
        swim(N);
     }
  
     public Item delMax() {
        Item max = pq[1];
        exch(1, N--);
        pq[N+1] = null;
        sink(1);
        return max;
     }
  
     private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
           exch(k/2, k);
           k = k/2;
        } 
     }
  
     private void sink(int k) {
        while (2*k <= N) {
           int j = 2*k;
           if (j < N && less(j, j+1)) j++;
           if (!less(k, j)) break;
           exch(k, j);
           k = j;
        }
     }
  
     private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
     }
  
     private void exch(int i, int j) {
        Item t = pq[i];
                 pq[i] = pq[j];
                         pq[j] = t;
     }
  
  }
  

• (Embora Comparable seja uma interface e não uma classe, podemos declarar variáveis como  Comparable x e Comparable[] x, como fizemos no código acima.)
• Para obter MinPQ troque delMax por delMin, troque less por greater, e implemente greater().
• Exemplo: Inserção e remoção em um heap decrescente:

  

• Proposição P. A altura de um heap com N nós é ⌊lg N⌋.
• Proposition Q. Em uma fila priorizada com N itens implementada com um heap,
  • cada inserção faz no máximo 1 + lg N comparações e
  • cada remoção do máximo faz no máximo 2 lg N comparações.

Exercícios 3

1. (SW 2.4.4)  Um vetor em ordem decrescente é um heap decrescente?  Um vetor em ordem crescente é um heap crescente?
2. (SW 2.4.15)  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.
3. (SW 2.4.5)  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.
4. (SW 2.4.6)  Mostre a sequência de heaps produzida pelas operações  P R I O * R * * I * T * Y * * * Q U E * * * U * E  aplicadas a um heap decrescente inicialmente vazio. (Uma letra significa inserção e um asterisco significa remoção do máximo.) Dê a sequência de letras produzida pelas remoções.
5. (SW 2.4.7)  O maior item de um heap decrescente deve estar na posição 1; o segundo maior deve estar na posição 2 ou na posição 3.  Suponha dado um heap de tamanho 31 sem itens repetidos. Para k = 2, 3, e 4, dê a lista de posições onde o k-ésimo maior item pode estar. Dê a lista de posições onde o k-ésimo maior item não pode estar.
6. (SW 2.4.9)  Desenhe todos os heaps que podem ser construídos com os itens  A B C D E .  Desenhe todos os heaps que podem ser construídos com os itens  A A A B B .
7. (SW 2.4.13)  Descreva uma maneira de evitar a comparação  j < N  no método sink().
8. (SW 2.4.26) Heap sem trocas. Como o método exch() é usado nas operações sink() e swim(), os itens são carregados e armazenados duas vezes mais que o necessário. Dê uma boa implementação que evite essa ineficiência.
9. (SW 2.4.27) Encontre o mínimo. Acrescente um método min() à classe MaxPQ. Sua implementação deve usar tempo constante e uma quantidade constante de espaço adicional.
10. (SW 2.4.29) 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.
11. (SW 2.4.11)  Suponha que sua aplicação terá um número enorme de operações insert e apenas algumas poucas operação delMax. Qual implementação de PQ devo usar: heap, vetor ordenado, ou vetor não ordenado?
12. (SW 2.4.12)  Suponha que sua aplicação terá um número enorme de operações max e apenas algumas poucas operação insert e delMax. Qual implementação de PQ devo usar: heap, vetor ordenado, ou vetor não ordenado?

Aplicações de filas priorizadas

• Escalonamento de tarefas (jobs) pelo sistema operacional de um computador.
• Algoritmo Heapsort (que ordena um vetor).
• Algoritmo de Dijkstra (que encontra um caminho de peso mínimo de um vértice s a um vértice t em um digrafo).
• Algoritmo de Prim (que encontra uma árvore geradora de peso mínimo em um grafo).
• Algoritmo de Kruskal (que encontra uma árvore geradora de peso mínimo em um grafo).
• Algoritmo de Huffman (de compressão de arquivos).
• Algoritmos de simulação. Experimente o simulador do movimento de partículas do capítulo 6 do livro:

  %java CollisionSystem 100
  
  %java CollisionSystem < billiards2.txt
  
  %java CollisionSystem < billiards4.txt
  
  %java CollisionSystem < brownian.txt
  
  %java CollisionSystem < diffusion.txt
  

  (Os arquivos da família billiards foram copiados de http://algs4.cs.​princeton.edu/​61event/.)

• Fotos de um instante das animações CollisionSystem < billiards.txt e CollisionSystem < diffusion.txt: