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.
Pontos a destacar:
-
API de fila priorizada crescente
-
API de fila priorizada decrescente
-
exemplo simples: as M maiores transações de uma longa lista
-
implementações em heap (operações sink() e swim())
-
aplicações
Pré-requisitos:
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
-
Critique a seaguinte definição alternativa de máximo:
um item é máximo se for maior
que todos os outros
.
-
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
-
(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
-
(SW 2.4.4)
Um vetor em ordem decrescente é um heap decrescente?
Um vetor em ordem crescente é um heap crescente?
-
(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.
-
(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.
-
(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.
-
(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.
-
(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 .
-
(SW 2.4.13)
Descreva uma maneira de evitar a comparação
j < N
no método sink().
-
(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.
-
(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.
-
(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.
-
(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?
-
(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:
Perguntas e respostas
-
Pergunta:
Qual a especificação do método compareTo()?
Resposta:
Se x e y são objetos de um tipo comparável,
ou seja, de um tipo que implementa a interface Comparable,
então
-
x.compareTo(y) é negativo se x é menor que y,
-
x.compareTo(y) é nulo se x é igual a y,
-
x.compareTo(y) é positivo se x é maior que y.
-
Pergunta:
O que significam as expressões ⌊x⌋
e ⌈x⌉ ?
Resposta:
A expressão ⌊x⌋
denota o piso do número x,
ou seja, o único inteiro i tal que
i ≤ x < i+1.
A expressão ⌈x⌉
denota o teto do número x,
ou seja, o único inteiro i tal que i−1 < x ≤ i.