Código Completo de HEAP binomial
#include<stdio.h>
#include<malloc.h>
struct noh {
int n;
int grau;
struct noh* pais;
struct noh* filha;
struct noh* irmao; };
struct noh* CRIAR_HEAP_bin();
int LIGA_bin(struct noh*, struct noh*);
struct noh* CRIAR_NOH(int);
struct noh* UNIAO_HEAP_bin(struct noh*, struct noh*);
struct noh* INSERIR_HEAP_bin(struct noh*, struct noh*);
struct noh* COMBINAR_HEAP_bin(struct noh*, struct noh*);
struct noh* EXTRAIR_MIN_HEAP_bin(struct noh*);
int REVERTER_LISTA(struct noh*);
int MOSTRAR(struct noh*);
struct noh* ENCONTRAR_NOH(struct noh*, int);
int DIMINUIR_CHAVE_HEAP_bin(struct noh*, int, int);
int EXCLUIR_HEAP_bin(struct noh*, int);
int cont = 1;
struct noh* CRIAR_HEAP_bin() {
struct noh* np;
np = NULL;
return np;
}
struct noh * H = NULL;
struct noh *Hr = NULL;
int LIGA_bin(struct noh* y, struct noh* z) {
y->pais = z;
y->irmao = z->filha;
z->filha = y;
z->grau = z->grau + 1; }
struct noh* CRIAR_NOH(int k) {
struct noh* p;//novo nó
p = (struct noh*) malloc(sizeof(struct noh));
p->n = k;
return p;
}
struct noh* UNIAO_HEAP_bin(struct noh* H1, struct noh* H2) {
struct noh* prev_x;
struct noh* prox_x;
struct noh* x;
struct noh* H = CRIAR_HEAP_bin();
H = COMBINAR_HEAP_bin(H1, H2);
if (H == NULL)
return H;
prev_x = NULL;
x = H;
prox_x = x->irmao;
while (prox_x != NULL) {
if ((x->grau != prox_x->grau) || ((prox_x->irmao != NULL)
&& (prox_x->irmao)->grau == x->grau)) {
prev_x = x;
x = prox_x;
} else {
if (x->n <= prox_x->n) {
x->irmao = prox_x->irmao;
LIGA_bin(prox_x, x);
} else {
if (prev_x == NULL)
H = prox_x;
else
prev_x->irmao = prox_x;
LIGA_bin(x, prox_x);
x = prox_x;}}
prox_x = x->irmao;}
return H;}
struct noh* INSERIR_HEAP_bin(struct noh* H, struct noh* x) {
struct noh* H1 = CRIAR_HEAP_bin();
x->pais = NULL;
x->filha = NULL;
x->irmao = NULL;
x->grau = 0;
H1 = x;
H = UNIAO_HEAP_bin(H, H1);
return H; }
struct noh* COMBINAR_HEAP_bin(struct noh* H1, struct noh* H2) {
struct noh* H = CRIAR_HEAP_bin();
struct noh* y;
struct noh* z;
struct noh* a;
struct noh* b;
y = H1;
z = H2;
if (y != NULL) {
if (z != NULL && y->grau <= z->grau)
H = y;
else if (z != NULL && y->grau > z->grau)
/* necessário algumas modificações aqui;
//a primeira e a outras condições pode se fundir!!!! */
H = z;
else
H = y;
} else
H = z;
while (y != NULL && z != NULL) {
if (y->grau < z->grau) {
y = y->irmao;
} else if (y->grau == z->grau) {
a = y->irmao;
y->irmao = z;
y = a;
} else {
b = z->irmao;
z->irmao = y;
z = b;}}
return H; }
int MOSTRAR(struct noh* H) {
struct noh* p;
if (H == NULL) {
printf("\nHEAP vazia");
return 0; }
printf("\nOs n%cs raizes s%co:-\n",162,198);
p = H;
while (p != NULL) {
printf("%d", p->n);
if (p->irmao != NULL)
printf("-->");
p = p->irmao;}
printf("\n");}
struct noh* EXTRAIR_MIN_HEAP_bin(struct noh* H1) {
int min;
struct noh* t = NULL;
struct noh* x = H1;
struct noh *Hr;
struct noh* p;
Hr = NULL;
if (x == NULL) {
printf("\nNada a ser extraido");
return x; }
// int min=x->n;
p = x;
while (p->irmao != NULL) {
if ((p->irmao)->n < min) {
min = (p->irmao)->n;
t = p;
x = p->irmao; }
p = p->irmao;}
if (t == NULL && x->irmao == NULL)
H1 = NULL;
else if (t == NULL)
H1 = x->irmao;
else if (t->irmao == NULL)
t = NULL;
else
t->irmao= x->irmao;
if (x->filha!= NULL) {
REVERTER_LISTA(x->filha);
(x->filha)->irmao = NULL;}
H =UNIAO_HEAP_bin(H1, Hr);
return x; }
int REVERTER_LISTA(struct noh* y) {
if (y->irmao != NULL) {
REVERTER_LISTA(y->irmao);
(y->irmao)->irmao = y;
} else {
Hr = y;}}
struct noh* ENCONTRAR_NOH(struct noh* H, int k) {
struct noh* x = H;
struct noh* p = NULL;
if (x->n == k) {
p = x;
return p;}
if (x->filha != NULL && p == NULL) {
p = ENCONTRAR_NOH(x->filha, k);}
if (x->irmao!= NULL && p == NULL) {
p = ENCONTRAR_NOH(x->irmao, k);}
return p;}
int DIMINUIR_CHAVE_HEAP_bin(struct noh* H, int i, int k) {
int temp;
struct noh* p;
struct noh* y;
struct noh* z;
p = ENCONTRAR_NOH(H, i);
if (p == NULL) {
printf("\nEscolha inv%clida da chave a ser reduzida",160);
return 0;
}
if (k > p->n) {
printf("\nA nova chave %c maior do que a atual",130);
return 0;}
p->n = k;
y = p;
z = p->pais;
while (z != NULL && y->n < z->n) {
temp = y->n;
y->n = z->n;
z->n = temp;
y = z;
z = z->pais;
}
printf("\nChave reduzida com sucesso!");}
int EXCLUIR_HEAP_bin(struct noh* H, int k) {
struct noh* np;
if (H == NULL) {
printf("\nHEAP vazia");
return 0;}
DIMINUIR_CHAVE_HEAP_bin(H, k, -1000);
np = EXTRAIR_MIN_HEAP_bin(H);
if (np != NULL)
printf("\nN%c excluido com sucesso",162);}
int main() {
int i, n, m, l;
struct noh* p;
struct noh* np;
char ch;
printf("\nEntre com o n%cmero de elementos:",163);
scanf("%d", &n);
printf("\nEntre com os elementos:\n");
for (i = 1; i <= n; i++) {
scanf("%d", &m);
np = CRIAR_NOH(m);
H = INSERIR_HEAP_bin(H, np);}
MOSTRAR(H);
do {
printf("\nMENU:-\n");
printf("\n1)Inserir um elemento\n2)Extrair um n%c chave minimo\n3)Diminuri uma chave n%c\n 4)Excluir um n%c\n5)Sair\n",162,162,162);
scanf("%d", &l);
switch (l) {
case 1:
do {
printf("\nEntre com elemento a ser inserido:");
scanf("%d", &m);
p = CRIAR_NOH(m);
H = INSERIR_HEAP_bin(H, p);
printf("Agora a Heap %c:\n",130);
MOSTRAR(H);
printf("\nInserir mais(y/Y)= \n");
fflush(stdin);
scanf("%c", &ch);
} while (ch == 'Y' || ch == 'y');
break;
case 2:
do {
printf("\nExtrair o n%c da chave minima",162);
p = EXTRAIR_MIN_HEAP_bin(H);
if (p != NULL)
printf("n%c extraido %c %d",162,130,p->n);
printf("\nAgora a Heap %c:\n",130);
MOSTRAR(H);
printf("\nExtrair mais(y/Y)\n");
fflush(stdin);
scanf("%c", &ch);
} while (ch == 'Y' || ch == 'y');
break;
case 3:
do {
printf("\nEntre com a chave de n%c a ser diminuido:",162);
scanf("%d", &m);
printf("\nEntre com a nova chave: ");
scanf("%d", &l);
DIMINUIR_CHAVE_HEAP_bin(H,m,l);
printf("\nAgora a Heap %c:\n",130);
MOSTRAR(H);
printf("\nDiminuir mais(y/Y)\n");
fflush(stdin);
scanf("%c", &ch);
} while (ch == 'Y' || ch == 'y');
break;
case 4:
do {
printf("\nEntre com a chave a ser excluida: ");
scanf("%d", &m);
EXCLUIR_HEAP_bin(H, m);
printf("\nDeletar mais(y/Y)\n");
fflush(stdin);
scanf("%c", &ch);
} while (ch == 'y' || ch == 'Y');
break;
case 5:
printf("\nAgrade%co a participa%c%co\n",135,135,198);
break;
default:
printf("\nEntrada inv%clida...Tente outra vez....\n",160); } } while (l != 5); }