Structuri de Date

L A B O R A T O R 7b

Heap nebinar

Un heap nebinar este o generalizare a unui heap binar, in care un nod interiorare M fii ( cu posibila exceptie a parintelui ultimului nod de pe ultimul nivel)Un heap nebinar este un vector in care se memoreaza un arbore nebinar completat nivel cu nivel si in care valoarea unui nod este mai mare (sau mai mica) cavalorile din nodurile fii. Fie vectorul "a" de n numere; radacina arborelui este a[1] si are ca fii pea[2],a[3],..a[M+1] (pozitia 0 din vector nu se foloseste). Parintele valorii a[i] este a[(i-2)/M+1], iar fiul numarul j al lui a[i]este a[M*(i-1)+j+1] (fii au indici j=1,2,..M). Valoarea a[0] nu apartine de vectorul heap.

Exemplu de minheap cu M=3 : 1,4,2,5,8,9,7,6,3 1 4 8 9 7 2 6 3 5

1. Sa se defineasca o structura "heap" care grupeaza un vector 'a' de intregide capacitate N (N este o constanta) si dimensiunea sa curenta 'n'. Sa se scrie functiile parent(i) si child(i,j) care au ca rezultat pozitia parintelui elementului din pozitia i si respectiv pozitia fiului j al elementului din pozitia i. Numarul de fii M va fi definit ca o constanta simbolica (cu valoarea 3 la inceput). Sa se scrie o functie care verifica daca vectorul din structura heap este unminheap, comparand fiecare element cu parintele sau: int verify(heap h);// 1=este, 0=nu este heap

Sa se scrie o functie "addHeap" care adauga o noua valoare la un minheapsi ridica in sus aceasta valoare cat este necesar pentru ca vectorul sa ramanaun minheap (prin schimbare cu parintele sau). Pseudocod pentru functia addHeap:

adauga x in prima pozitie libera (i=++h.n) p= parent(i) //indice parinte nod i repeta cat timp i>1 si x< valoare [p] { schimba valoare[i] cu valoare[p] i=p// verifica pentru noua pozitie a lui x p=parent(i)// parinte i }

Sa se scrie o functie "makeHeap" care creeaza un minheap prin adaugareasuccesiva de elemente din vectorul x folosind functia "addHeap": void makeHeap(heap & h, int x[], int n);Pentru verificare se va folosi functia "verify".

2. Sa se scrie o functie "indmin" care determina indicele valorii minime dintreelementul din pozitia i si cei M fii ai sai: int indmin (heap h,int i);

Sa se scrie functiile "heapify"(recursiv) si "heapify2" (iterativ) pentru un minheap de numere intregi:

void heapify (heap & h, int k) { // ajustare arbore cu radacina in k m=indmin (h,k) daca m != k atunci { schimba a[k] cu a[m] heapify(h,m) // ajustare subarbore cu radacina in m } }

Sa se scrie functiile "makeHeap1" si "makeHeap2" care construiesc un minheapdintr-un vector dat x folosind functiile "heapify" si respectiv "heapify2".

void makeHeap1 (heap & h,int x[], int n) { for (i= (h.n+1)/M; i>=1; i--) heapify (h,i); }

3. Sa se scrie o functie recursiva "prefix" care sa afiseze vectorul heap ca arbore in ordine prefixata si cu indentare diferita la fiecare nivel: void prefix (heap h,int k,int sp); // k=indice radacina , sp=nr de spatiiApelul din "main": prefix(h,1,0); Sa se scrie o functie de ordonare a unui vector x prin creare minheap urmatade scoaterea si afisarea valorii minime in mod repetat: void heapsort (int x[], int n);

Sa se verifice cu programul urmator folosind succesiv M=3,4,2

int main () { heap h; int n=50; int x[100]={0}; int i; for (i=1;i