DEV Community: Amanda Fonseca

Heap - Min e Max

Amanda Fonseca — Wed, 30 Oct 2024 23:19:09 +0000

Heap - Min Heap

Heap é uma versão mais eficiente da lista de prioridade. Leve em consideração so métodos de inserção e remoção da Priority Queue Sorted e Unsorted, na Unsorted inserir custa O(1), já remover custa O(n), já a Sorted inserir custa O(n) e remover O(1).

	sorted	unsorted
insert	O(n)	O(1)
remove	O(1)	O(n)

Heap é construída por um Array, mas sua representação é uma árvore binária, o elemento com mais prioridade fica no topo, a raiz. Ela é preenchida de cima para baixo e da direita para esquerda, sem filhos faltando!

🧠

Contudo, há a possibilidade de se construir a estrutura de dados com a maior prioridade ser definida pelo maior valor de key. Nesse caso tem-se o max heap, que veremos posteriormente.

Min_Heap

Para ser uma Heap válida é preciso que todos os elementos filhos tenham menor ou igual prioridade que os pais. Além disso, ela deve estar completa sem filhos faltando, caso contrário, o array terá um espaço em branco.

🧠

Uma maneira mais formal de realizar esta definição é dizer que uma árvore binária é completa se seus níveis 0, 1, 2, · · · h − 1 possuem o máximo de elementos possíveis e os elementos existentes no nível h se encontram alocados ao máximo à esquerda possível.

Como citado, heap é constituido por um array (representado em verde), mas pode ser visualizada como uma estrutura de árvore, conforme a imagem abaixo.

Há duas formas de montar a Heap, com o primeiro elemento na posição 0, ou sem a posição 0, nesse artigo veremos a diferença dos dois casos. Os elementos de cima sempre tem seus filhos, vulgo elementos em baixo, para descobrir esses filhos, no caso de ter o index 0, pode ter essasinformações utlizando esses cálculo:

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

Caso use versão com o 0 não preenchido basta diminuir a soma, ou seja, +1-1=0, no caso parent fica index / 2.

Insert

Sempre se adiciona no final, a única preocupação que deve ter é na hora da checagem se o elemento filho tem menor key que o pai, para isso é executado o bubbling up (borbulhar) que é quando compara as Keys do elemento inserido e do pai, trocando se necessário.

Falando com mais detalhes, coloca o elemento no ultimo espaço vazio da árvore e, como precisa comparar a key dele com a do pai, precisamos calcular o index do pai para termos acesso do key do mesmo. Para sabermos o pai, usa o calculo citado:

parent = (indexDoFilho -1)/2

E para tal, falta o indexDoFilho: para obter tal, pegamos uma variavel para ser o index atual, como estamos no insert que é adição no final, o index atual é o ultimo, sendo:

currentIndex = size-1

Agora tendo o index atual, chama o Parent e assim descobre quem é o pai do elemento que ta sendo inserido. Queremos o pai desse novo elemento pois, para organizar a árvore de maneira certa, esse elemento deve ser comparado com o seu pai e, se sua key for menor, eles devem trocar de local.

Enquanto o index atual for maior que 0 (visando evitar pegar um index indisponível) e o index atual for menor que o index do pai, se essa condição for verdadeira, o elemento precisa ser trocado com o pai para garantir a propriedade da heap mínima e então ocorre a troca (Swap) e então o index atual recebe o index do pai, e então pega o pai do pai (KKKKK) para . O Swap é um método que usa a estrutura de uma troca de valores normal.

public void insert(K key, V value) { //o(log n)
    if (isFull()){
        throw new RuntimeException("full");
    }
    //adc a entry na ultima posição do vetor
    heap[size++]=new PriorityEntry(key, value);
    //guarda o index que esse novo elemento tá
    int currentIndex = size-1;
    //chama o método parent pra calcular quem é o pai do novo elemento
    int parent = parent(currentIndex);
    //percorre enquanto o index nao for o 0 e o index ser 
    while (currentIndex>0 && compare(currentIndex, parent)<0){
        swap(currentIndex, parent);
        currentIndex = parent;
        parent = parent(currentIndex);
    }
}

Sendo parente:

protected int parent(int index){
        return (index-1)/2;
}

Sendo swap um método de troca de valores normal:

protected void swap(int index1, int index2){
    Entry auxEntry = heap[index1];
    heap[index1] = heap[index2];
    heap[index2] = auxEntry;
}

Se o valor do elemento atual (filho) for menor que o valor do pai, isso indica que a propriedade da heap mínima foi violada. Numa heap mínima, o pai sempre deve ser menor ou igual ao filho. Quando essa condição não é satisfeita, o filho deve trocar de lugar com o pai para que o valor menor continue "subindo" na heap até encontrar a posição correta, onde a propriedade será mantida.

Remove

Remove o elemento de index 0, mas a árvore deixa de ficar completa! Para resolver isso, puxa o ultimo elemento do array para o começo, ou seja, o ultimo elemento que foi adicionado vai pro topo da árvore. Após isso, faz a checagem de novo, só que agora de cima para baixo. Ou seja, agora é a vez de comparar os pais com os filhos! (sinkdown)
O método sinkDown() move o elemento para baixo (ou “afunda”) na heap, até que ele esteja na posição correta, onde seu valor é menor ou igual ao de seus filhos (caso esteja em uma posição com filhos).
No sinkDown existe uma variável para armazenar o index do elemento de menor key começando na raiz e outra pro index atual. Em seguida, um loop que durará até o index do elemento atual ser igual ao index do elemento de menor key. Dentro do loop pega os filhos do atual e ver se os filhos estão dentro do intervalo do array e se o index do filho for menor que o index do mínimo atualiza o mínimo.

private void sinkDown(){
        int current, min = 0;
        int leftChild, rightChild;
        do{
            current = min;
            leftChild = leftChild(current);
            rightChild = rightChild(current);
            if(leftChild < size && compare(leftChild, min)<=0){
                min = leftChild;
            }
            if(rightChild<size && compare(rightChild, min)<0){
                min = rightChild;
            }
            swap(current, min);
        }while(current!=min);
    }

No caso:

@Override
    public Entry<K, V> dequeue() {
        Entry<K,V> auxEntry = maxPriority();
        heap[0] = heap[--size];
        if(size>1){
            sinkDown();
        }
        return auxEntry;
    }

Resumo:

Propriedades da Min Heap:

Estrutura de árvore binária completa.
O nó pai sempre possui valor igual ou menor que seus nós filhos.
Implementada via array, onde a posição dos filhos e do pai é determinada por fórmulas baseadas no índice.

Para calcular posições dos filhos e pais:

Esquerda: leftChild = index * 2 + 1
Direita: rightChild = index * 2 + 2
Pai: parent = (index - 1) / 2

Versão sem o índice 0: Basta subtrair 1 dos cálculos, resultando em:

leftChild = index * 2
rightChild = index * 2 + 1
parent = index / 2

Heap - Max Heap

O mairo valor fica na raiz, assim, o nó pai tem o valor igual ou maior que seus filhos

As fórmulas para calcular filhos e pais:

Esquerda: leftChild = index * 2 + 1
Direita: rightChild = index * 2 + 2
Pai: parent = (index - 1) / 2

Insert

Adiciona o elemento no final e faz o bubbling up, que seria a comparação do elemento com seu pai trocando de local se necessário. O(log n).

public void enqueue(K key, V value) {
    if (isFull()) throw new FullQueueException("Heap is full!");
    heap[size++] = new PriorityEntry(key, value);
    int current = size - 1;
    int parent = parent(current);
    while (current > 0 && compare(current, parent) > 0) { // Para max heap
        swap(current, parent);
        current = parent;
        parent = parent(current);
    }
}

Remove

Remove o elemento heapMax[0], vulgo a raiz, e então pega o ultimo elemento e sobe ele para a raiz, chamando o sinkdown em seguida, empurrando o novo elemento da raiz para baixo até encontrar sua posição correta.

sinkDown precisa garantir que o valor no nó pai seja maior ou igual aos valores nos nós filhos. Portanto, ao afundar um nó, ele será comparado com o filho maior.

No Min Heap, sinkDown deve assegurar que o valor no nó pai seja menor ou igual aos valores dos filhos. Nesse caso, a comparação é feita com o filho menor.

public Entry<K, V> dequeue() {
    if (isEmpty()) throw new EmptyQueueException("Heap is empty!");
    Entry<K, V> max = heap[0];
    heap[0] = heap[--size];
    if (size > 1) sinkDown();
    return max;
}

private void sinkDown() {
    int current = 0;
    while (true) {
        int leftChild = leftChild(current);
        int rightChild = rightChild(current);
        int largest = current;

        if (leftChild < size && compare(leftChild, largest) > 0) { // Verifica se o filho esquerdo é maior
            largest = leftChild;
        }
        if (rightChild < size && compare(rightChild, largest) > 0) { // Verifica se o filho direito é maior
            largest = rightChild;
        }

        if (largest == current) break; // Se o atual for o maior, a estrutura está correta

        swap(current, largest);
        current = largest; // Move para o próximo filho
    }
}

Diferenças

No Max Heap, sinkDown precisa garantir que o valor no nó pai seja maior ou igual aos valores nos nós filhos. Portanto, ao afundar um nó, ele será comparado com o filho maior.
No Max Heap, se o nó pai é menor que o maior dos filhos, então ele deve trocar com o maior filho para garantir que o maior valor esteja o mais alto possível.
No Min Heap, sinkDown deve assegurar que o valor no nó pai seja menor ou igual aos valores dos filhos. Nesse caso, a comparação é feita com o filho menor.
No Min Heap, a troca ocorre se o nó pai é maior que o menor dos filhos, mantendo o menor valor no topo

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

Amanda Fonseca — Sun, 20 Oct 2024 22:06:18 +0000

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)