Priority Queue! Vamos destrinchar e aprender sobre essa parte de Estrutura de Dados.

Fila

Fila, assim como a Pilha, é uma especialização da Lista. Ela basea-se no fundamento FIFO - first in, first out, isso significa que o primeiro a entrar é o primeiro a sair. Em outras palavras, o mais “velho” da fila sai primeiro, para melhor compreensão leve em consideração uma fila de banco.

⚠️

Aplicações da Fila: Gerenciamento de processos em sistemas operacionais; Comunicação entre tarefas em programação concorrente; redes de computadores (impressões); respostas de requisições em servidor Web

Filas em si só permite a manipulação direta de dados nas extremidades.

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

Fila de Prioridade

Assemelha-se ao comportamento de uma fila comum do dia a dia, mas agora encare que você está na fila de um banco e uma senhora entra na fila, todos deixam ela passar na frente pois a mesma tem maior PRIORIDADE por ser mais velha.

Na Estrutura de Dados Priority Queue cada nó tem um Key-Value, Key é a chave que guarda sua prioridade, Value é o valor do nó. Por padrão do Java, a Key é inicialmente numérica, podendo ser trocada pelo programador posteriormente.

O conjunto de uma Key e Value se chama Entry, logo a interface dessa E.D muda. Outros detalhes são: após a Key ser definida, ela não pode ser alterada. Caso dois nós tenham o mesmo valor de prioridade na Key o programador escolhe a regra.

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

Nas próximas estruturas, iremos usar as classes para Node e Entry, atributos de first, last e size, e o compareTo

A fila de prioridade se divide em dois: a ordenada (Sorted Priority Queue) e a desordenada (Unorted Priority Queue)

Sorted Priority Queue

Lista ordenada se preocupa logo em inserir o nó na posição certa, logo a remoção é fácil, só remover o primeiro (se o programador fazendo a E.D definir que o elemento de maior prioridade deve ficar no começo)

Para sabermos qual nó tem maior prioridade usamos compareTo, uma função de Collections que, através de seu retorno, podemos obter resultados cruciais para a execução dessa E.D, caso o retorno seja:

• Negativo: Se o objeto que chama o método é "menor" que o objeto passado como parâmetro.
• Zero: Se os objetos são iguais.
• Positivo: Se o objeto que chama o método é "maior" que o objeto passado como parâmetro.

Insert

Para inserir deve verificar algumas coisas

1° passo → Criar um novo nó

Node newNode = new Node(key, value)

2° passo → Verificar se a Fila está vazia, se sim, colocar o Head e o Last como o novo nó, tendo em vista que será o único

        if(isEmpty()){
            first = newNode;
            last = newNode;
        }else{

3° passo → Se não for o único elemento da lista, deve verificar se o novo nó, comparado com o primeiro, tem maior prioridade ou não.

         if(compare(newNode, first)<0){
                 //Se o nN for menor que o F
                 //Levando em consideração que a prioridade maior é 0
                 //Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
                newNode.next = first;
                first.previous = newNode;
                first = newNode;
          }

3° passo → Compara depois com o último elemento da lista

             }else if(compare(newNode, last)>=0){
           //Se o nN for maior que o L
           //Significa que o número de nN é maior que L
           //Então bota o nN para ultimo
                newNode.previous=last;
                last.next=newNode;
                last = newNode;
            }else{

4° passo → Se não for todo o resto, só resta o meio! Para tal ato, precisamos fazer um nó auxiliar para ir percorrendo na frente do newNode (nN) e ir comparando os dois, a comparação acaba quando o auxNode aponta para nada, ou quando o nN for maior que o auxNode (maior, logo fica atrás dele na fila). Esse while serve para o aux ir andando e comparando o valor dos dois nós, quando achar, coloca o nN atrás do auxNode

            }else{
                //se nao for nada, está no meio
                //entao temos que achar entre qual dos meios
                Node auxNode = first;
                while(compare(newNode, auxNode)>0 && auxNode.next!=null){
                    //enquanto o newNode tiver prioridade maior que o auxiliar
                    //e o auxiliar tiver um proximo
                    auxNode = auxNode.next;
                }
                newNode.next = auxNode;
                newNode.previous = auxNode.previous;
            }
        }

Remove

O método remover no Sorted é bem mais simples pois, como já fora dito, a Fila já está toda organizada para ele.

1° passo → Como todo método Remove retorna o elemnto que ele irá tirar, o passo será criar uma Entry (Por que não um nó?)

        Entry<K,V> max = maxPriority();

2° passo → Depois, como já vai eliminar o primeiro nó, basta apontar o First para o próximo do First

        first = first.next;

3° passo → Ver se tem só um elemento na Fila, pois se tiver, a Fila ficará vazia! Logo terá que apontar para null o F e L

        if(size==1){
            last = null;
            first = null;
        }else{

4° passo → Se não for o único elemento, significa que tem outros! Logo, quando tirar o primeiro no passo 2, o que antes era First ainda está lá sendo ligado pelo previous, então devemos:

       else{
            first.previous = null;
        }
        return max;

MaxPriority

Método que retorna o elemento de maior prioridade da lista, e como estamos na ordenada, apenas retorna o primeiro.

    public Entry<K,V> maxPriority(){
        if(isEmpty()) throw new RuntimeException("PQ is empty!");
        return first.entry;
    }

Análise Assintótica

Método	O(_)
size	O(1)
isEmpty	O(1)
insert	O(n)
remove	O(1)
maxPriority	O(1)

Unsorted Priority Queue

A Fila desordenada é bem diferente da ordenada! Comecemos por seus métodos:

Insert

Para adicionar na unsorted, como e desordenada, não precisa se preocupar em qual local esse novo elemento vai ficar, apenas adiciona no final!

1° passo → Verifica se a lista está vazia, pois se estiver, o nó a ser adicionado será o primeiro (First) e o último (Last)

       Node newNode = new Node(key, value);
       if(isEmpty()){
        //se tiver vazia significa que vai ser o primeiro elemento
        first = newNode;
       }else{

2° passo → se não for vazia, basta se preocupar em adicionar esse nó no final!

       }else{
        //se não for vazia, vai ser adicionado no final
        newNode.previous = last;
        last.next = newNode;
       }
       last = newNode;
       size++;

MaxPriority

O remove em Unsorted é bem mais complexo do que as míseras linhas de código do Sorted…

“Por quê?” você pergunta, devemos usar um método ( que na outra versão era bem mais simples também) chamado maxPriority, cujo objetivo é achar o nó de maior prioridade. Anteriormente ele foi ensinado de maneira simples com poucas linhas de código, agora, por não sabermos onde de fato está esse nó de maior prioridade, devemos percorrer a fila toda em busca dele! Então antes de vermos o remove em si, veremos o maxPriority.

1° passo → Sempre que queremos percorrer uma estrutura de dados, precisamos de dois nós: um auxiliar para ir sempre na frente, e o que queremos atingir (que nesse caso é o MaxPriority)

        Node max = first;
        Node aux = first.next;

2° passo → Esses dois irão percorrer dentro de um nó, só acaba quando o aux chegar ao null (final da fila). Faz o compare desses nós e se for negativo siginica que o aux é menor que o max, logo o max é o maior, atualizando o valor do max Node, e então faz o aux andar.

        while (auxNode!=null) {
           int c = compare(auxNode, maxPriority);
            if(c<0){
                maxPriority = auxNode;
            }
           auxNode = auxNode.next;
        }
        return maxPriority;

Remove

1° passo → Em todos os emoves é criar uma variável que vai guardar o nóque vai ser removido. Nesse caso, já sabe qual será removido pois está chamando o método maxPriority

        Node toRemove = maxPriorityNode();

2° passo → Depois verifica se é o único elemento, se sim, F e L são nulls!

        if(size==1){
            //se só tem um elemento da fila, significa q ela fica vazia
            first = null;
            last = null;

3° passo → Se não for o único, há outras opções: se o max for o ultimo, elimina last, se for o primeiro, elimina o first, se não for nenhum dois dois, está no meio!

        }else{
            if(max == first){
                //se o max for o primeiro elemento, tira do começo
                first = first.next;
                first.previous = null;
            }else if(max == last){
                //se o max for o último elemento, tira do final
                last = last.previous;
                last.next = null;
            }

4° passo → Se estiver no meio, o max que está no povão terá que ser retirado, isso ocorre quando ninguém mais apontar para ele.

            }else{
                //se o max não for o primeiro ou o último, tira do meio
                max.previous.next = max.next;
                max.next.previous = max.previous;
            }
        }
        return max.entry;

Análise Assintótica

Método	O(_)
size	O(1)
isEmpty	O(1)
insert	O(1)
remove	O(n)
maxPriority	O(n)