Twoja wyszukiwarka
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define Minimum 0
#define Maximum 1
typedef struct Element
{
int key;
int poz;
}Element;
typedef struct Element* HeapEl;
typedef struct Heap
{
int max_size;
int size;
HeapEl* heaps;
}Heap;
Heap* kopiec;
void init() //funkcja inicjalizujaca
{
HeapEl* object;
kopiec = (Heap*) malloc(sizeof(Heap));
object = (HeapEl*) malloc(sizeof(HeapEl));
kopiec->size = 0;
kopiec->max_size = 1;
kopiec->heaps = object;
}
void zamien(int poz1, int poz2) //funkcja zamieniajaca dwa podane elementy
{
HeapEl temp_entry;
((kopiec->heaps)[poz1])->poz = poz2;
((kopiec->heaps)[poz2])->poz = poz1;
temp_entry = (kopiec->heaps)[poz1];
(kopiec->heaps)[poz1] = (kopiec->heaps)[poz2];
(kopiec->heaps)[poz2] = temp_entry;
}
void porzadek_dodanie_min(int poz) //funkcja, ktora sprawdza porzadek w kopcu (poziomow Min) po dodaniu wezla
{
int lvl;
int changed=0;
int parent = (poz - 1) / 2; //rodzic dla wskazanego wezla (co drugi poziom) - tylko minimum
while (poz > 0)
{
if ( ((kopiec->heaps)[parent]->key < (kopiec->heaps)[poz]->key) && changed==0 ) //Jesli klucz rodzica jest mniejszy niz przekazany klucz to nastepuje zamiana
{
zamien(poz, parent);
poz = parent;
lvl=Maximum;
}
changed = 1;
parent = (((poz - 1) / 2)-1)/2;
if(lvl==Minimum) //Jesli wezel znajduje sie na poziomie Minimum
{
if ( ((kopiec->heaps)[parent]->key > (kopiec->heaps)[poz]->key) ) //Jesli klucz rodzica jest wiekszy niz klucz elementu
{
zamien(poz, parent); //zamieniamy
poz = parent;
changed = 1;
lvl=Minimum; //ustawiamy poziom jako minimum
}else{poz=0;}
}else
{
if ( ((kopiec->heaps)[parent]->key < (kopiec->heaps)[poz]->key) && parent!=0 ) //jesli rodzic jest mniejszy niz element i rozny od 0
{
zamien(poz, parent);
poz = parent;
lvl=Maximum; //poziom maximum
}else{poz=0;}
}
}
}
void porzadek_dodanie_max(int poz) //funkcja sprawdzajaca porzadek w kopcu (porzadek max)
{
int changed;
int lvl;
changed=0;
int parent = (poz - 1) / 2;
while (poz > 0)
{
if ( ((kopiec->heaps)[parent]->key > (kopiec->heaps)[poz]->key) && changed==0 )
{
zamien(poz, parent);
poz = parent;
lvl=Minimum;
}
changed = 1;
parent = (((poz - 1) / 2)-1)/2;
if(lvl==Minimum)
{
if ( ((kopiec->heaps)[parent]->key > (kopiec->heaps)[poz]->key) )
{
zamien(poz, parent);
poz = parent;
changed = 1;
lvl=Minimum;
}else{poz=0;}
}else{
if ( ((kopiec->heaps)[parent]->key < (kopiec->heaps)[poz]->key) && parent!=0 )
{
zamien(poz, parent);
poz = parent;
lvl=Maximum;
}else{poz=0;}
}
}
}
void porzadek_dodanie(int poz) //Funkcja porzadkujaca kopiec po dodaniu
{
int lvl;
lvl = (int)floor(log2(poz+1));
if (poz >= kopiec->size) //Jesli przeslana poz jest wieksza od rozmiaru - Error
{
printf("Blad - przekroczono rozmiar kopca");
return;
}
if((lvl % 2) == Maximum) //Jesli parzyste to maximum, else minimum
{
porzadek_dodanie_max(poz);
}else
{
porzadek_dodanie_min(poz);
}
}
//funkcja sprawdzajaca czy na danym poziomie jest mniejsza (wieksza) wartosc
int zamienMinMaxOnLvl(int act_ind, int lvl, int type)
{
int i,start, stop, num, ind, act;
act = kopiec->heaps[act_ind]->key;
start = 4*act_ind + 3;
stop = start + 3;
ind = start;
if(start > kopiec->size) return -1;
num = kopiec->heaps[ind]->key;
if(type == Maximum)
{
if(stop > kopiec->size) stop = kopiec->size;
for(i=start; i<=stop; i++ )
{
if (kopiec->heaps[i]->key > num) {num = kopiec->heaps[i]->key;ind = i;}
}
if(act < num)
{
return ind;
}else
{
return -1;
}
}else{
if(stop > kopiec->size) stop = kopiec->size;
for(i=start; i<=stop; i++ ){
if (kopiec->heaps[i]->key < num) {num = kopiec->heaps[i]->key;ind = i;}
}
if(act > num){
return ind;
}else{
return -1;
}
}
}
void porzadek_del_min(int poz) //funkcja porzadkujaca kopiec po odjeciu min
{
int maxlvl,lvl,right,left, parent, ctr,tmp, smaller;
lvl = (int)floor(log2(poz+1)) + 2; //obliczenia poziomu na podstawie pozycji
maxlvl = (int)floor(log2(kopiec->size));
ctr=1;
while (ctr>0)
{
if(lvl <= maxlvl)
{
tmp = zamienMinMaxOnLvl(poz,lvl, Minimum);
}
else{tmp=-1;}
if(tmp>0)
{
zamien(poz, tmp);
poz=tmp;
lvl+=2;
}else
{
ctr=-1;
}
}
parent = (poz - 1) / 2;
left = 2 * poz + 1;
right = left + 1;
smaller = right;
if (right > kopiec->size - 1){
smaller = left;
}else if (((kopiec->heaps)[left])->key < ((kopiec->heaps)[right])->key){
smaller = left;
}
if ((smaller <= kopiec->size - 1) && (((kopiec->heaps)[smaller])->key < ((kopiec->heaps)[poz])->key) ){
zamien(poz, smaller);
poz = smaller;
}
if(kopiec->heaps[parent]->key < kopiec->heaps[poz]->key)
{
zamien(poz, parent);
}
}
void porzadek_del_max(int poz) //porzadkujemy kopiec po skasowaniu wezla na poziomie max
{
int maxlvl,lvl,right,left, parent, ctr,tmp, bigger;
lvl = (int)floor(log2(poz+1)) + 2;
maxlvl = (int)floor(log2(kopiec->size));
ctr=1;
while (ctr>0)
{
if(lvl <= maxlvl)
{
tmp = zamienMinMaxOnLvl(poz,lvl, Maximum);}
else
{
tmp=-1;
}
if(tmp>0){
zamien(poz, tmp);
poz=tmp;
lvl+=2;
}else{
ctr=-1;
}
}
parent = (poz - 1) / 2;
left = 2 * poz + 1;
right = left + 1;
bigger = right;
if (right > kopiec->size - 1){
bigger = left;
}else if (((kopiec->heaps)[left])->key > ((kopiec->heaps)[right])->key){
bigger = left;
}
if ((bigger <= kopiec->size - 1) && (((kopiec->heaps)[bigger])->key > ((kopiec->heaps)[poz])->key) ){
zamien(poz, bigger);
poz = bigger;
}
if(kopiec->heaps[parent]->key > kopiec->heaps[poz]->key)
{
zamien(poz, parent);
}
}
int deleteMin()
{
int tmp;
if (kopiec->size <= 0)
{
return 0;
}else
{
tmp = ((kopiec->heaps)[0])->key;
(kopiec->size)--;
zamien(0,kopiec->size);
porzadek_del_min(0);
return tmp;
}
}
int deleteMax()
{
int tmp,ind;
if (kopiec->size <= 0)
{
return 0;
}else{
if((kopiec->heaps)[1]->key > (kopiec->heaps)[2]->key)
{
ind=1;
}
else{
ind=2;
}
tmp = ((kopiec->heaps)[ind])->key;
(kopiec->size)--;
zamien(ind,kopiec->size);
porzadek_del_max(ind);
return tmp;
}
}
void addItem(int key)
{
HeapEl nowy_element;
HeapEl* new_ptr_table;
nowy_element = (HeapEl)malloc(sizeof(Element));
nowy_element->key = key; //wstawianie nowego elementu
nowy_element->poz = kopiec->size; //na najnizszym poziomie kopca
if(kopiec->size == kopiec->max_size)
{
(kopiec->max_size)*=2;
new_ptr_table = (HeapEl *)realloc(kopiec->heaps, (kopiec->max_size)*sizeof(HeapEl));
kopiec->heaps = new_ptr_table;
}
(kopiec->heaps)[kopiec->size] = nowy_element;
(kopiec->size)++;
porzadek_dodanie(kopiec->size-1); //uporzadkowanie
}
void print()
{
if(kopiec->size > 0)
{
int i,parent;
for(i=0;i < (kopiec->size);i++)
{
parent = (i - 1) / 2;
printf("Parent: %d ",((kopiec->heaps)[parent])->key);
printf("Key: %d \n",((kopiec->heaps)[i])->key);
}
}
}
int main(int argc, char** argv)
{
int liczba,x,y;
init();
srand(time(0));
// addItem(5);
// addItem(10);
// addItem(3);
// addItem(1);
// addItem(2);
int i=0;
while(i<10000)
{
liczba = rand()%15000+1;
if(liczba>0)
{
addItem(liczba);
i++;
}
}
i=0;
while(1)
{
i++;
x=deleteMax();
y=deleteMin();
if(x==0 && y==0) break;
printf("Wartosc klucza usuwanego (max) (%d): %d \n",i,x);
printf("Wartosc klucza usuwanego (min) (%d): %d \n",i,y);
}
system("pause");
return 1;
}