Heap Ağacı
//8.Bölüm-Ağaçlar (Heap Ağacı)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
struct dugum
{
int key;
//İstenilen diğer bilgiler.
};
struct heap
{
struct dugum *dizi;
int kapasite; //Toplam düğüm sayısı. Tutulabilecek en fazla eleman sayısı.
int eleman_sayisi;
};
struct heap *heap_olustur(int kapasite)
{
struct heap *gecici;
gecici=(struct heap *)malloc( sizeof(struct heap) );
if(!gecici)
{
printf("Dinamik alan ayirma basarisiz...");
exit(1);
}
gecici->dizi=(struct dugum *)malloc( kapasite*sizeof(struct dugum) );
if(!gecici->dizi)
{
printf("Dinamik alan ayirma basarisiz...");
exit(1);
}
gecici->kapasite=kapasite;
gecici->eleman_sayisi=0;
return gecici;
}
/*
void heap_olustur_yeni(struct heap **h,int kapasite)
{
*h=(struct heap *)malloc( sizeof(struct heap) );
if(!*h)
{
printf("Dinamik alan ayirma basarisiz...");
exit(1);
}
(*h)->dizi=(struct dugum *)malloc( kapasite*sizeof(struct dugum) );
if(!(*h)->dizi)
{
printf("Dinamik alan ayirma basarisiz...");
exit(1);
}
(*h)->kapasite=kapasite;
(*h)->eleman_sayisi=0;
}
*/
void print_heap(struct heap *heap)
{
int i;
for(i=0;i<heap->eleman_sayisi;i++)
printf("%4d",heap->dizi[i].key);
printf("\n");
}
void initialize_heap(struct heap *heap,int eleman_sayisi,int aralik)
{
int i,j;
int yeni,cik;
srand(time(NULL)); //Her defasında farklı sayılar üretilir.
heap->dizi[0].key=rand()%aralik;
for(i=1;i<eleman_sayisi;i++)
{
while(1)
{
cik=1;
yeni=rand()%aralik;
for(j=0;j<i;j++) //Öncei anahtarlar kontrol edilmektedir.
{
if(yeni==heap->dizi[j].key)
{
cik=0;
break;
}
}
if(!cik) //cik==0
continue;
heap->dizi[i].key=yeni;
break;
}
}
heap->eleman_sayisi=eleman_sayisi;
}
void buble_down(struct heap *heap,int index)
{
int sol,sag;
sol=2*index+1;
sag=2*index+2;
int temp_key;
while( (sol < heap->eleman_sayisi && heap->dizi[index].key < heap->dizi[sol].key) || (sag < heap->eleman_sayisi && heap->dizi[index].key < heap->dizi[sag].key) )
{ /*Sol düğümün olup olmadığı kontrol edilir.
İlk kısım doğruysa ya sağı büyüktür, ya da solu büyüktür.*/
if(sag>=heap->eleman_sayisi || heap->dizi[sol].key > heap->dizi[sag].key) //Sağı yoksa || soldaki sağdakinden büyükse.
{
temp_key=heap->dizi[sol].key;
heap->dizi[sol].key=heap->dizi[index].key;
heap->dizi[index].key=temp_key;
index=2*index+1;
}
else
{
temp_key=heap->dizi[sag].key;
heap->dizi[sag].key=heap->dizi[index].key;
heap->dizi[index].key=temp_key;
index=2*index+2;
}
sol=2*index+1;
sag=2*index+2;
}
}
void heapify(struct heap *heap)
{
int i;
for(i=heap->eleman_sayisi/2-1;i>=0;i--)
buble_down(heap,i);
}
void buble_up(struct heap *heap,int index) //Eklenen eleman sonrası heap özelliği bozulması sonucu (bozulmayabilir) heap özellği kazandırılıyor.
{
int parent,temp_key;
parent=(index-1)/2;
while(parent>=0 && heap->dizi[parent].key < heap->dizi[index].key)
{
temp_key=heap->dizi[parent].key;
heap->dizi[parent].key=heap->dizi[index].key;
heap->dizi[index].key=temp_key;
index=parent;
parent=(index-1)/2;
}
}
void heap_insert(struct heap *heap,int key)
{
if(heap->eleman_sayisi < heap->kapasite)
{
heap->eleman_sayisi++;
heap->dizi[heap->eleman_sayisi - 1].key=key;
buble_up(heap,heap->eleman_sayisi - 1);
}
}
void delete_max(struct heap *heap) //Sürekli uygulanarak dizi sıralı hale getirilebilir.
{
int temp_key;
if(heap->eleman_sayisi > 1)
{
temp_key=heap->dizi[0].key;
heap->dizi[0].key=heap->dizi[heap->eleman_sayisi - 1].key;
heap->dizi[heap->eleman_sayisi - 1].key=temp_key;
heap->eleman_sayisi--;
buble_down(heap,0);
}
}
void heap_sort(struct heap *heap)
{
int i;
int temp=heap->eleman_sayisi;
for(i=1;i<temp;i++)
delete_max(heap);
heap->eleman_sayisi=temp;
}
int main(int argc, char** argv)
{
struct heap *heap=heap_olustur(20);
/*
struct heap *h1=NULL;
heap_olustur_yeni(&h1,kapasite);
*/
initialize_heap(heap,10,101); //10 tane elaman.
print_heap(heap); //31 87 67 74 9 35 1 47 20 46
heapify(heap);
print_heap(heap); //87 74 67 47 46 35 1 31 20 9
heap_sort(heap);
print_heap(heap); //1 9 20 31 35 46 47 67 74 87
/*
heap_insert(heap,55);
heap_insert(heap,75);
print_heap(heap);
*/
getch();
return 0;
}
No comments:
Post a Comment