A estrutura de heap é uma forma de organizar os seus dados de forma que o acesso seja prático e rápido. Existem dois tipos de heaps, o heap de máximo e o heap de mínimo. Os heaps de mínimo geralmente são usados para implementar filas de prioridade, que eu não vou falar por aqui mas quem sabe num próximo post. Já o de máximo é o mais usado para fazermos uso do Heapsort, que é a forma de ordenar os dados no formato de heap.
Porém antes de falar de heap é preciso falar de árvores binárias, pois o heap nada mais é do que uma árvore binária balanceada. Árvores binárias são uma estrutura de dados em que os objetos são organizados de forma em que existe um nó, e esse nó pode ter um ou dois filhos (Os filhos da esquerda e os filhos da direita). Tomemos o seguinte exemplo:
#include <iostream>
using namespace std;
struct node{
int num;
node *esq = NULL;
node *dir = NULL;
};
void prefix(node* raiz){
if(raiz != NULL){
cout << " " << raiz->num;
prefix(raiz->esq);
prefix(raiz->dir);
}
}
void insert(node *no, int val){
if(no->num < val){
if(no->dir == NULL){
node* dir = new node;
dir->num = val;
no->dir = dir;
}
else{
insert(no->dir,val);
}
}
else{
if(no->esq == NULL){
node* esq = new node;
esq->num = val;
no->esq = esq;
}
else{
insert(no->esq, val);
}
}
}
int main(){
int nos;
cin >> nos;
node* raiz = NULL;
for(int i=0;i<nos;i++){
int val;
cin >> val;
if(raiz == NULL){
raiz = new node;
raiz->num = val;
}
else{
insert(raiz,val);
}
}
cout << "Prefixa:";
prefix(raiz);
cout << endl;
}No código acima usamos struct, que nos permite criar uma nova estrutura, é como se criássemos um novo tipo de dado como inteiros,strings,floats. Nessa struct que eu chamei de node, temos 3 atributos. O primeiro indica o valor do nó, e o segundo e o terceiro indicam respectivamente seus filhos a esquerda e direita (Repare que inicialmente um nó não tem filhos, por isso ambos são nulos). Temos a função insert, que olha se um determinado valor deve ser inserido a esquerda ou a direita e depois o insere no local correto fazendo uso de recursão. No fim fazemos uso da função prefix, isso porque existem algumas formas de imprimir os valores de uma árvore, nesse caso estamos usando o formato em que primeiro imprimimos a raiz, depois todos os elementos a esquerda da raiz e por fim todos a direita.
No main eu apenas fiz de uma forma que o usuário pode decidir quantos elementos ele quer em sua árvore e quais são esses valores. Lembrando que uma árvore binária pode ser feita de qualquer tipo de dado, não necessariamente apenas de inteiros.
Como podem ver é bem tranquilo. Seria interessante treinar e estudar um pouco mais sobre arvore binária, entender direito como ela funciona, pois é uma estrutura muito útil para otimização do código e aumento de velocidade em sua aplicação. Existem questões interessantes no uri sobre isso:
