Binary Heap
Espera, não é mais uma postagem do guia dos calouros?
Pois é, pela primeira vez, estou aqui fazendo uma postagem para ensinar um conteúdo de nível intermediário (ou pelo menos tentar). Após escrever algumas postagens ensinando o básico de programação para calouros, acredito que tenha conseguido certa experiência em ensinar alguma coisa através de postagens escritas. Sendo assim, hora de começar a ensinar temas mais complexos e encher o site com diversas postagens úteis para todos os níveis de programadores. O nível da vez é um nível de programador competitivo que está saindo do básico e se dirigindo ao nível intermediário. Essa certamente será a minha primeira postagem que irá requerer um esforço maior, já que precisarei buscar fontes para melhorar o conteúdo que irei passar aqui, portanto o nível da postagem tem a tendência de ser melhor que as postagens do Guia dos Calouros.
Requisitos
Para ser capaz de entender totalmente essa postagem, é necessário conhecer os seguintes conceitos:
- Recursividade
Também é recomendado conhecer um pouco da biblioteca padrão do C++, para melhor compreender os códigos que serão expostos nessa postagem.
Introdução
Hoje vamos falar sobre Binary Heap, que é uma estrutura de dados capaz de representar um array em forma de árvore balanceada.
Para representar a árvore em forma de array, utilizamos a seguinte técnica:
- Representamos o nó da árvore no elemento $0$ do array
- O pai do nó $i$ está no índice $(i-1) // 2$
- Os filhos à esquerda do nó $i$ são inseridos no índice $2i + 1$
- Os filhos à direita do nó $i$ são inseridos no índice $2i + 2$
O Binary Heap possui outra característica, que é a de respeitar a condição de Heap, sendo esta dependente do tipo de Heap que estamos implementando.
Tipos de Heap
Existem basicamente dois tipos de Heap:
- Heap máximo ou max-heap: $\forall i \in \{2,3,...,heapSize\}, heap[parent(i)] \geq heap[i]$. Ou seja, para todo nó do Binary Heap não sendo a raiz, o valor do pai desse nó é maior ou igual ao valor desse nó.
- Heap mínimo ou min-heap: $\forall i \in \{2,3,...,heapSize\}, heap[parent(i)] \leq heap[i]$. Ou seja, para todo nó do Binary Heap não sendo a raiz, o valor do pai desse nó é menor ou igual ao valor desse nó.
Sendo assim, em um max-heap o elemento de maior valor sempre será a raiz da árvore, enquanto que em um min-heap o elemento de menor valor sempre será a raiz da árvore.
Construindo o Binary Heap
Agora que sabemos o conceito de Binary Heap, vamos pensar como podemos construir um Binary Heap que obedeça a propriedade do tipo de Heap escolhido (min/max-heap). Suponhamos um vetor inicial $V = \{8, 10, 2, 27, 38, 29, 42\}$ e que estamos construindo um max-heap. Ao inserir o primeiro elemento, a propriedade de heap se mantém, tendo $heap = \{8\}$. Quando inserirmos o segundo elemento de $A$, acabaremos estragando a propriedade de heap, já que $8 \ngeq 10$. Sendo assim, precisamos trocar o 8 e o 10 de lugares, tendo como resultado $heap = \{10, 8\}$. Continuando a construir o Binary Heap, teremos:
- Elemento inserido: $2$ | $heap = \{10, 8, 2\}$
- Elemento inserido: $27$ | $heap = \{27, 10, 2, 8\}$
- Elemento inserido: $38$ | $heap = \{38, 27, 2, 8, 10\}$
- Elemento inserido: $29$ | $heap = \{38, 27, 29, 8, 10, 2\}$
Agora, vamos analisar com calma a inserção do elemento 42. Ele será inicialmente inserido como nó a direita do nó que guarda o número 29, quebrando assim a propriedade de Heap, já que $29 \ngeq 42$. Com isso, temos que mudar o 29 e o 42 de lugar e, como o nó 29 mantinha a propriedade de Heap em sua sub árvore até inserirmos o valor 42 e $42 \geq 29$, logo a sub árvore que possui 42 como raiz manterá a propriedade de Heap. Da mesma forma vai ocorrer quando trocarmos 42 com 38, restabelecendo a propriedade de Heap. Assim, para implementarmos a construção do Binary Heap, para cada nó que inserirmos, percorremos dele até a raiz, buscando chegar a raiz ou alcançar a propriedade de Heap sem precisar fazer a troca.
Uma possível implementação disso em C++ seria:
int parent(int x){
return (x-1)>>1;
}
void insert_heap(std::vector<int>& heap, int x){
int i = heap.size();
heap.push_back(x);
while (i != 0 && heap[parent(i)] < heap[i]){
std::swap(heap[parent(i)], heap[i]);
i = parent(i);
}
}
Criamos assim uma função para inserir elementos em um Binary Heap. Supondo que nós já tenhamos um array pré definido do qual queremos aplicar a propriedade de Heap nele, podemos fazê-lo com uma função que percorre esse array e vai inserindo elementos no Heap:
std::vector<int> build_heap(std::vector<int>& array){
std::vector<int> heap;
for (int i = 0; i < array.size(); i++){
insert_heap(heap, array[i]);
}
return heap;
}
Mantendo a propriedade de Heap
Agora que sabemos construir o Binary Heap, podemos pensar o que podemos fazer com ele. Sabemos que para tirarmos o maior ou menor elemento, dependendo da implementação, basta pegarmos o valor da raiz do Heap. Mas e se quisermos saber o segundo, terceiro, quarto maior/menor elemento, como fazemos? Para isso, precisamos remover o elemento do topo do Binary Heap e restabelecer a propriedade de heap. Para isso, existem alguns passos que podemos seguir:
- Trocamos o nó raiz do Binary Heap com o último nó, para então excluirmos esse elemento;
- Percorremos o Binary Heap da raiz para as folhas recursivamente, verificando a propriedade de heap;
- Para cada nó, verificamos qual filho é o maior e, se ele for maior que o nó atual, realizamos a troca.
Uma possível implementação dessas funções em C++ é a seguinte:
int esquerda(int x){
return (x<<1)+1;
}
int direita(int x){
return (x<<1)+2;
}
void restore_heap(std::vector<int>& heap, int i){
int e = esquerda(i);
int d = direita(i);
int maior = i;
if (e < heap.size() && heap[e] > heap[i]) maior = e;
if (d < heap.size() && heap[d] > heap[maior]) maior = d;
if (maior != i){
std::swap(heap[i], heap[maior]);
restore_heap(heap, maior);
}
}
int get_max(std::vector<int>& heap){
return heap[0];
}
void exclude_max(std::vector<int>& heap){
std::swap(heap[0], heap[heap.size()-1]);
heap.pop_back();
restore_heap(heap, 0);
}
A implementação da min_heap é análoga, bastando modificar as condições presentes na função restore_heap() para que as propriedades de Heap Mínimo sejam mantidas.
Complexidade
Falando por cima da complexidade, as complexidades de tempo dessa implementação de Binary Heap para o pior caso são:
- Inserir valor no Heap: $\theta\ (log\ n)$
- Construção do Heap: $\theta\ (n\ log\ n)$
- Restaurar propriedade do Heap: $\theta\ (log\ n)$
- Excluir valor do Heap: $\theta\ (log\ n)$
Aplicações do Binary Heap
O Binary Heap possui duas aplicações principais, cada uma para uma propriedade de heap. O min-heap pode ser utilizado para implementar uma estrutura de fila de prioridade, que mantém os elementos ordenados e garante que o elemento a sair da fila será sempre o menor elemento. O max-heap pode ser utilizado para implementar o algoritmo de ordenação heapsort. Além disso, a forma de representação do Binary Heap pode ser utilizado mais adiante para explicar outros assuntos, como Segment Tree e Fenwick Tree.
Como não encontrei nenhum exercício relacionado especificamente ao tema (e confesso que não estou com muita vontade de ir atrás, quem sabe mais pra frente atualizo a postagem), deixo aqui como tarefa implementar a fila de prioridade e o heapsort, que apesar de já estarem presentes na biblioteca padrão, pode ser um bom exercício para fixar o conteúdo. Ah, e tente implementar o Binary Heap do zero, sem copiar o código que eu exemplifiquei ali, para conseguir fixar a representação de árvore binária em arrays.
Referências
CORMEN, Thomas H. et al. Introduction to algorithms. MIT press, 2009. 3ª ed. p. 151-153
https://www.geeksforgeeks.org/binary-heap/. Acesso em 11/02/2021