HeapFuncoes Linguagem c

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

#include <stdio.h>
#include <limits.h>
#include <string.h>
// Linguagem C 
#define TAM 100
#define left(i) ((i)<<1)
#define right(i) (((i)<<1)+1)
#define pai(i) ((i)>>1)
typedef struct {
	int tamanho;
	int elemento[TAM];
} Heap;
void troca(int * a, int * b) {
	int temp;
	temp = * a;
	* a = * b;
	* b = temp;
}
//garante manter a propriedade max heap abaixo do indice i
void funcHeap(Heap * A, int i) {
	int maior= A->elemento[i];
	int posicao = i;
	int l = left(i);
	if(l <= A->tamanho && A->elemento[l] > maior) {
		maior= A->elemento[l];
		posicao = l;
	}
	int r = right(i);
	if(r <= A->tamanho && A->elemento[r] > maior) {
		maior= A->elemento[r];
		posicao = r;
	}
	if(i != posicao) {
		troca(&A->elemento[i], &A->elemento[posicao]);
		funcHeap(A, posicao);
	}
}
//
int extractMax(Heap * A) {
	if(!A->tamanho) {
		printf("vazio");
		return 0;
	}
	int max = A->elemento[0];//no max-heap sempre o primeiro e maior
	troca(&A->elemento[0], &A->elemento[A->tamanho]);//ultimo elemento
	--A->tamanho;
	funcHeap(A, 0);//para arrumar de volta,ficar como max-heap
	return max;
}
//muda a chave do elemento do indice
void increaseKey(Heap * A, int i, int k) {
	int posicao = i;
	while(posicao != 0 && A->elemento[pai(posicao)] < k) {//chave maior
		A->elemento[posicao] = A->elemento[pai(posicao)];//troca o pai
		posicao = pai(posicao);
	}
	A->elemento[posicao] = k;//filho da posicao recebe o valor do pai
}
//insere valor na heap A
void insert(Heap * A, int i) {
	if(A->tamanho >= TAM) {
		printf("heap jah esta cheia\n");
		return;
	}
	A->elemento[A->tamanho] = INT_MIN;// ultimo elemento - infinido
	increaseKey(A, A->tamanho, i);
	++A->tamanho;
}
//mostra o vetor
void mostra(Heap * A) {
	int i = 0;
	for(i = 0; i < A->tamanho; i++) {
		printf(" %d ", A->elemento[i]);
	}
}
void buildHeap(Heap * A, int * a, int n) {//para contruir uma max-heap, pode estar tudo desorganizado
	if(n > TAM) {
		printf(" \n a mais elementos que o tamanho\n");
		return;
	}
	int nbytes = n * sizeof(int);//pega o tamanho da variavel,cada inteiro 2
	memcpy(A->elemento, a, nbytes);//copia valores de a para A->elemento
	A->tamanho = n;
	int i = 0;
	for(i = A->tamanho/2; i >= 0; i--) {//max-heap
		funcHeap(A, i);
	}
}
int main() {
	Heap someHeap = {0, {0}};
	Heap * A = &someHeap;
	mostra(A);
	int i,valor,tam=4,a[tam];
 //insert
 printf("\n insert \n");
 for(i=0;i<tam;i++){
 scanf("%d",&valor);
 a[i]=valor;
 }
	buildHeap(A, a, tam);
	mostra(A);
	//printf("%d\n", extractMax(A));
printf("\n \n");
	//inserindo na posicao escolida
	printf("\n maior %d\n", extractMax(A));
	int valor2=100,posicao=0;
	a[posicao]=valor2;
 buildHeap(A, a, tam);
	mostra(A);
	printf("\n maior %d\n", extractMax(A));
	return 0;
}