Heap - Min e Max

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

Comments

[Boopathi]

This is a great explanation of the Min Heap data structure! It's especially helpful to see the visual representation and code examples. I'm looking forward to learning more about Max Heaps in the next post.