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:

Pré-requisitos:

Introdução

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

Implementações elementares

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

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


Perguntas e respostas


Valid CSS! Valid HTML 4.01 Strict