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_s , h_s+1 , , h_d  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₂ , ., h₁₅ 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 h_i al ansamblului ii corespunde locatia h[i].

h₁

h₂ h₃

h₄ h₅ h₆ h₇

h₈ h₉h₁₀ h₁₁ h₁₂ h₁₃ h₁₄h₁₅

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₁ , ., h_n) .

Se presupune un ansamblu h_s+1 , h_s+2 , ., h_d definit prin indicii s +1 si d 

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

34

h₁ 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  h₂ , ., h₇ , iar in aceeasi figura (b), ansamblul extins spre stanga cu un element x = 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()