Max-Heap
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176
#include <stdio.h>
/*
Criação e controle de MAX-HEAP
Em uma arvore max-heap todos os elementos filhos são menores que os pais,
em uma min-heap ocorro o contrário. Não há uma distinção de lados, ou seja,
tanto o filho a direita quanto o à esquerda podem ser o maior, desde que não
sejam maiores que o pai.
Ex:
CORRETO ERRADO
(Filho menores que os pais) (10 e 25 tem filhos maiores)
40 40
/ \ / \
15 30 10* 25*
/ \ / \ / \ / \
5 10 25 20 15 5 30 20
Como o comportamento da heap é sempre igual, pode-se representar uma heap com
um array.
*/
//Constante de capacidade total de armazenamento
#define CAPACITY 15
//Tamanho inicia em -1
int size = -1;
//Inicia Heap, colocando valor padrão de -1
void createHeap(int heap[]){
for(int i = 0; i < CAPACITY;i++){
heap[i] = -1;
}
}
/*Retorna filho a esquerda
*O filho a esquerda sempre será o dobro da posição + 1
*/
int getL(int pos){
return (int) 2 * pos+1;
}
/*Retorna filho a direita
*O filho a direita sempre será o dobro da posição + 2
*/
int getR(int pos){
return (int) 2 * pos+2;
}
/*Retorna o pai
*O pai sempre será metade da posição-1
*/
int getP(int pos){
return (int) (pos-1)/2;
}
/* Inverte os números nas posições x e y
*Para ordenar uma heap será necessário fazer várias trocas
*/
void swap(int heap[],int x, int y){
int aux = heap[x];
heap[x] = heap[y];
heap[y] = aux;
}
//Retona o maior elemento do heap
int getMax(int heap[]){
if(size > -1){
return heap[0];
}else printf("Impossivel obter maior número, array vazio!\n");
}
/* Após inserir um item é preciso ver se ele não é maior que seu pai,
caso seja será necessário inverte-los de posição. Após a troca é preciso
verificar novamente se o pai não é menor que filho até que não haja mais
trocas para serem feitas.
*/
void heapfyUp(int heap[],int pos){
//Caso não seja a raiz
if(pos > 0){
//Caso o pai seja menor que filho, faz a troca
if(heap[getP(pos)] < heap[pos])
swap(heap,getP(pos),pos);
//Chama a função novamente agora passando a posição do pai
heapfyUp(heap,getP(pos));
}
}
/* Para remover um elemento é preciso coloca-lo no final da lista para só depois
remove-lo. Após isso é necessário verificar se o elemento que foi trocado de
lugar está corretamente posicionado, verificando se ele não é menor que os
seus filhos, caso seja ocorrem trocas até que a heap esteja correta.
*/
void heapfyDown(int heap[],int pos){
//Verifica se o elemento não é uma folha
if(heap[pos] > -1){
//Se o pai for menor que o filho a esquerda
if(heap[pos] < heap[getL(pos)]){
//Faz a troca
swap(heap,pos,getL(pos));
//Chama a função para o filho a esquerda
heapfyDown(heap,getL(pos));
}
//Se o pai for menor que o filho a direita
if(heap[pos] < heap[getR(pos)]){
//Faz a troca
swap(heap,pos,getR(pos));
//Chama a função para o filho a direita
heapfyDown(heap,getR(pos));
}
}
}
//Insere valor e ordena
void insert(int n,int heap[]){
//Aumenta o tamanho da heap
size++;
//Insere valor no final
heap[size] = n;
//Ordena a heap de baixo para cima
heapfyUp(heap,size);
}
//Remove valor e ordena
void removeItem(int pos,int heap[]){
//Coloca o valor a ser removido no final da heap
swap(heap,pos,size);
//Remove o item
heap[size] = -1;
//Diminui o tamanho da heap
size--;
//Ordena a heap de cima para baixo
heapfyDown(heap,0);
}
//Mostra valores inseridos
void show(int heap[]){
printf("Heap: ");
for(int i = 0; i <= size; i++){
if(i < size)
printf("%d - ",heap[i]);
else
printf("%d",heap[i]);
}
}
int main(void) {
int maxHeap[CAPACITY];
createHeap(maxHeap);
insert(5,maxHeap);
insert(10,maxHeap);
insert(15,maxHeap);
insert(20,maxHeap);
insert(25,maxHeap);
insert(30,maxHeap);
insert(35,maxHeap);
show(maxHeap);
printf("\nRemovendo 35...\n");
removeItem(0,maxHeap);
show(maxHeap);
printf("\nAdicionando 40...\n");
insert(40,maxHeap);
show(maxHeap);
return 0;
}
C
INFO