#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; }