Filas priorizadas

Veja as páginas Filas priorizadas (PF) e Priority queues (S&W).

Um fila priorizada mantém itens/chaves/objetos comparáveis em ordem decrescente ou crescente. Assim, precisamos utilizar o método compareTo(). Por isso é que Key extends Comparable<Key>, ou seja, objetos da classe Key devem possuir o método compareTo().

Podemos implementar filas priorizadas em vetores e lista ordenadas e não ordenadas. Entretanto, a estrutura de dados mais manjada para representarmos filas priorizadas são Heaps de máximo ou de mínimo.

Em relação a estrutura, heaps binários utilizam um vetor para representar uma árvore binária quase completa. Cada nó de uma árvore binária tem até dois filhos. Bem, poderíamos usar uma ideia semelhante para representar em um vetor uma árvore d-ária quase completa (árvore com até d filhos). O "quase completa" se deve ao fato de todos os nós internos terem exatamente dois filhos com a possível exceção de apenas um nó, aquele do "cantinho", que pode ter apenas um filho.

Chamamos os nós da árvore são 1,2,3,...,n, em referência ao índice do vetor que contém o item/chave. Assim, temos que os filhos de um nó i são 2*i e 2*i+1 e que o pai de um nó i > 1 é i/2. O nó 1 é a raiz e não tem pai. Para ser um heap de máximo devemos ter que a chave no nó pai de i é maior ou igual a chave no nó i, para todo i > 1. Os nós 1,2,...,n/2-1 têm exatamente 2 filhos, o nó n/2 pode ter 1 ou 2, dependendo da paridade de n (verificar). n/2 é o tal nó interno do "cantinho".

As operações básicas para manutenção um heap são swim() e sink().

As operações sobre um heap consomem tempo proporcional a lgn: inserir (insert()), remover máximo (delMax())/mínimo(delMin()), alterar a prioridade de um nó.

Hmm, não falamos sobre heaps em que a prioridade de uma chave pode ser alterada. Precisaremos desse chamados index priority queues mais para frente em alguns algoritmos em grafos.

Há muitos exercícios bacanas sobre árvores priorizadas.

• Exercises: todos os exercícios dessa seção estão feitos e são fundamentais. O exercício 20 mostra como construir um heap a partir de uma lista de chaves. Esse é o que vocês usaram no heapSort() em MAC0121. É meio facil ver que o consumo de tempo é não superior a n lg n, já que aplica sink() n vezes. Dá um pouco mais de trabalho mostrar que na verdade consome tempo linear.
• Creative problems: Vejam pelo menos os exercícios com solução.
• Web exercises: Bem, já falei de muitos exercícios, olhem alguns daqui.

P.S. Tem muito material para estudar. A ideia dos exercícios que tem solução é você ler o exercício, pensar em uma solução e, só depois de pensar, ver a solução. O tempo que você vai gastar pensando depende do seu interesse, teimosia , tempo disponível, etc.