Structuri de Date

L A B O R A T O R 7a MinHeap binar

Un minheap este un vector cu urmatoarele proprietati:- Valoarea fiecarui nod este mai mica sau egala cu valorile din nodurile fii,deci valoarea minima se afla in radacina arborelui.- Valoarea din pozitia k are fiul stanga in pozitia 2*k si fiul dreapta inpozitia 2*k+1. Parintele valorii din pozitia k este in pozitia k/2. Exemple de vectori minheap de lungime 4 construiti cu valorile 1,2,3,4 :

1,3,2,4 1,2,3,4 1,2,4,3

1 1 1 / \ / \ / \ 3 2 2 3 2 4 / / / 4 4 3

Adaugarea unui nou element la un vector Heap se face in prima pozitie libera(de la sfarsitul vectorului), dupa care se ridica acest element in vector astfel ca sa se respecte conditia de minheap.

addH (x) { k=++n; // k este prima pozitie libera pune x in pozitia k repeta cat timp k>1 si a[k/2]>a[k] { // daca a[k] mai mic ca parintele sau schimba a[k] cu a[k/2] k=k/2 } }

La extragerea si eliminarea valorii minime dintr-un minheap (primul element)se aduce apoi ultimul element in prima pozitie, dupa care se corecteaza vectorul pentru respectarea conditie de heap (prin propagarea in jos a valorii din prima pozitie, cat timp este necesar):

delH { x=a[1]// prima valoare e minima a[1]=a[n--] // se aduce ultima valoare la inceput heapify(1)// refacere heap return x }

Operatia "heapify" se poate exprima recursiv sau iterativ: se determina repetat valoarea maxima dintre elementele a[k], a[2*k] si a[2*k+1] si, daca e nevoie, se aduce acest maxim in pozitia k. Notand cu a vectorul si cu n dimensiunea sa, forma recursiva este:

heapify(k) { // ajustare arbore cu radacina in k m=indmin (k) // indice minim dintre a[k],a[2k],a[2k+1] daca m != k atunci { schimba a[k] cu a[m] heapify(m) // ajustare subarbore cu radacina in m } }

Varianta iterativa a functiei anterioare este:

heapify(k) { repeta cat timp e necesar un interschimb { m=indmin (k) // indice maxim dintre a[k],a[2k],a[2k+1] daca m != k atunci{ schimba a[k] cu a[m] k=m } } }

Observatie: inainte de a folosi indicii 2*k si 2*k+1 se verifica daca exista acesti indici in vector (daca sunt inferiori lui n).

indmin (k) { st=2*k, dr=st+1 m=k// indice val. minima (initial k) daca st