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