This content originally appeared on DEV Community and was authored by Amanda Fonseca
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 * 2rightChild = index * 2 + 1parent = 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,
sinkDownprecisa 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,
sinkDowndeve 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
This content originally appeared on DEV Community and was authored by Amanda Fonseca
Amanda Fonseca | Sciencx (2024-10-30T23:19:09+00:00) Heap – Min e Max. Retrieved from https://www.scien.cx/2024/10/30/heap-min-e-max/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.