Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Meseria se fura, ingineria se invata.Telecomunicatii, comunicatiile la distanta, Retele de, telefonie, VOIP, TV, satelit




Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Informatica


Index » educatie » Informatica
Tehnica rezolvarii prin metoda ansamblelor heap-sort


Tehnica rezolvarii prin metoda ansamblelor heap-sort


Tehnica rezolvarii prin metoda ansamblelor heap-sort

  • Un ansamblu ('heap') este definit ca o secventa de chei h, hs+1 , , hd care se bucura de proprietatile [3.2.5.a]:

    pentru toti i = s, , d/2
  • Un ansamblu poate fi asimilat cu un arbore binar partial ordonat si reprezentat printr-un tablou.
  • Spre exemplu, ansamblul h, h, ., h15 poate fi asimilat cu arborele binar din figura 3.2.5.d si poate fi reprezentat prin tabloul h in baza urmatoarei tehnici:
    • Se numeroteaza elementele ansamblului, nivel cu nivel, de sus in jos, de la stanga la dreapta;
    • Se asociaza elementelor ansamblului, locatiile unui tablou de elemente h, astfel incat elementului hi al ansamblului ii corespunde locatia h[i].

h1



h2 h3



h4 h5 h6 h7




h8 h9h10 h11 h12 h13 h14h15


1 2 34 56 7 89 10 11 1213 14 15
















Fig. 3.2.5.d. Reprezentarea unui ansamblu printr-un tablou liniar h

  • Un ansamblu se bucura de proprietatea ca primul sau element este cel mai mic dintre toate elementele ansamblului adica h= min (h, ., hn.

Se presupune un ansamblu hs+1 , hs+2 , ., hd definit prin indicii s +1 si d 

Acestui ansamblu i se adauga la stanga, pe pozitia hs un nou element x , obtinandu-se un ansamblu extins spre stanga hs , , h.


34


h1 04



2204 2212




6583 1812 65 8318 34


1 2 3 456 7 1 2 3 4567


(a) (b)


Fig. 3.2.5.e. Deplasarea unei chei intr-un ansamblu

In figura 3.2.5.e.(a) apare ca exemplu ansamblul  h2 , ., h, iar in aceeasi figura (b), ansamblul extins spre stanga cu un element = 34 .

    • Noul ansamblu se obtine din cel anterior plasand pe x in varful ansamblului si deplasandu-l 'in jos' de-a lungul drumului indicat de componentele cele mai mici, care in acelasi timp urca.
    • Astfel valoarea 34 este mai intai schimbata cu valoarea 04, apoi cu valoarea 12, generand structura din figura amintita.
    • Se poate verifica cu usurinta ca aceasta deplasare conserva conditiile care definesc un ansamblu [3.2.5.a].

sortare prin metoda ansamblelor - heapsort - varianta C

deplasare(int s,int d)

a[i-1]=x;

} [3.2.5.h]


heapsort()









Politica de confidentialitate





Copyright © 2023 - Toate drepturile rezervate