Algoritmul HeapSort

• HeapSort este unul din algoritmii de sortare foarte performanti, fiind de clasa O(N·log₂N)
• Mai este cunoscut sub denumirea de “sortare prin metoda ansamblelor”
• Desi nerecursiv, este aproape la fel de performant ca si algoritmii de sortare recursivi (QuickSort fiind cel mai cunoscut)
• HeapSort este un algoritm de sortare “in situ”, adica nu necesita structuri de date suplimentare, ci sortarea se face folosind numai spatiul de memorie al tabloului ce trebuie sortat
• Exista si implementari HeapSort care nu sunt “in situ”

Calin Jebelean

Algoritmul HeapSort

1

Algoritmul HeapSort

• Algoritmul se aseamana, in unele privinte, cu sortarea prin selectie (SelSort)
• La fiecare pas, cel mai mic element din tablou este gasit si mutat in spatele tabloului, fiind ignorat de pasii urmatori, care vor continua pe restul tabloului
• Diferenta fata de SelSort este ca pasii urmatori ai algoritmului vor depune un efort mai mic (chiar mult mai mic) pentru a depista minimul din tabloul ramas
• Fiecare pas al algoritmului are darul de a usura sarcina pasilor ce urmeaza, ceea ce duce la performanta foarte buna a algoritmului

Calin Jebelean

Algoritmul HeapSort

2

Algoritmul HeapSort

• Gasirea minimului din tablou, operatie ce are loc la fiecare pas, se bazeaza pe aducerea tabloului la forma de ansamblu
• Un ansamblu este un sir A_i (i = 1 … N) care indeplineste urmatoarele conditii pentru fiecare i:
• A_i ≤ A_2·i
• A_i ≤ A_2·i+1
• Evident, pentru valori ale lui i mai mari decat N/2 nu se pune problema indeplinirii conditiilor de mai sus

Calin Jebelean

Algoritmul HeapSort

3

Algoritmul HeapSort

• Orice tablou poate fi transformat usor intr-un arbore binar

Calin Jebelean

Algoritmul HeapSort

4

1

2

3

4

5

6

7

8

Index:

A₁

A₂

A₃

A₄

A₅

A₆

A₇

A₈

A:

A₁

A₂

A₃

A₄

A₅

A₆

A₇

A₈

9

A₉

A₉

Algoritmul HeapSort

• Daca tabloul era ansamblu, se observa ca arborele binar obtinut indeplineste urmatoarea conditie: “fiecare nod are cheia mai mare sau egala cu a tatalui sau”.
• Astfel, A₂ si A₃ sunt mai mari sau egale cu A₁, A₄ si A₅ sunt mai mari sau egale cu A₂, s. a. m. d.
• Dar A₁ este radacina arborelui binar, ceea ce inseamna ca A₁ trebuie sa fie elementul minim al tabloului
• Deci intr-un ansamblu, elementul minim se afla intotdeauna pe prima pozitie
• In cadrul algoritmului HeapSort, daca la fiecare pas aducem tabloul pe care lucram la forma unui ansamblu inseamna ca am localizat in acelasi timp si minimul din tablou

Calin Jebelean

Algoritmul HeapSort

5

Algoritmul HeapSort

• Aducerea unui tablou la forma de ansamblu se face urmarind situatii cum este cea descrisa mai jos:

​

​

​

• Daca nu este indeplinita una din conditiile A_i ≤ A_2·i si A_i ≤ A_2·i+1 atunci se va interschimba A_i cu minimul dintre A_2·i si A_2·i+1
• Elementele astfel interschimbate vor indeplini conditia de ansamblu
• Pentru o eficienta cat mai mare, urmarirea acestui gen de situatii trebuie facuta de la dreapta la stanga, in caz contrar fiind nevoie de reveniri repetate chiar si dupa ce o situatie de neconcordanta a fost rezolvata

Calin Jebelean

Algoritmul HeapSort

6

1

Index:

A₁

A:

i

A_i

…

…

…

…

2·i+1

A_2·i+1

2·i

A_2·i

…

…

N

A_N

Algoritmul HeapSort

• Vom studia, pas cu pas, modul in care un tablou oarecare poate fi transformat in ansamblu
• Aceasta transformare se va aplica la fiecare pas in cadrul algoritmului HeapSort, pe un tablou din ce in ce mai mic (deoarece dupa fiecare pas, primul element al tabloului, care este elementul minim, va fi eliminat si “pus la pastrare”, algoritmul continuand pe restul tabloului)
• Pentru simplitate, vom lucra pe reprezentarea sub forma de arbore a tabloului:

Calin Jebelean

Algoritmul HeapSort

7

1

2

3

4

5

6

7

8

Index:

9

5

1

8

6

4

3

7

A:

9

2

Algoritmul HeapSort

​

​

​

​

​

​

​

• Problema se pune numai pentru noduri neterminale
• Localizam cel mai de jos nod neterminal, si in caz ca sunt mai multe astfel de noduri, il consideram pe cel mai din dreapta – acesta este 8
• Cum 8 are fiii 7 si 2 si este mai mare decat ambii, se va interschimba cu cel mai mic dintre ei, adica cu 2

Calin Jebelean

Algoritmul HeapSort

8

9

5

1

8

6

4

3

7

2

Algoritmul HeapSort

​

​

​

​

​

​

​

• Urmatorul nod neterminal este 1 (nodul 5 este pe acelasi nivel, dar il alegem intotdeauna pe cel mai din dreapta in astfel de cazuri)
• Nodul 1 este mai mic decat fiii sai, deci nu va face obiectul vreunei interschimbari
• Trecand la nodul 5, acesta nu indeplineste conditiile, ca atare va fi interschimbat cu cel mai mic fiu al sau, anume 2

Calin Jebelean

Algoritmul HeapSort

9

9

5

1

2

6

4

3

7

8

Algoritmul HeapSort

​

​

​

​

​

​

​

• Inainte de a trece la noul nod neterminal, verificam ca ultimul nod interschimbat (5) sa indeplineasca conditia referitoare la fiii sai (7 si 8) – se observa ca o indeplineste
• Noul nod neterminal este 9
• Acesta nu indeplineste conditiile, fiind mai mare si decat 2 si decat 1, ca atare, 9 va fi interschimbat cu cel mai mic, deci cu 1

Calin Jebelean

Algoritmul HeapSort

10

9

2

1

5

6

4

3

7

8

Algoritmul HeapSort

​

​

​

​

​

​

​

• S-ar putea ca ultimul nod interschimbat (9) inca sa nu indeplineasca conditiile referitoare la fiii sai, in noua sa locatie
• 9 fiind mai mare si decat 4 si decat 3, se va interschimba cu 3 (cel mai mic)
• Astfel de interschimbari repetate vor avea loc pana cand 9 ajunge pe un nivel pe care fiii sai sunt mai mari sau egali cu el (sau pe un nivel unde nu mai are fii)

Calin Jebelean

Algoritmul HeapSort

11

1

2

9

5

6

4

3

7

8

Algoritmul HeapSort

​

​

​

​

​

​

​

• 9 a ajuns pe un nivel terminal (nu mai are fii) deci nu mai continuam in jos
• In acest moment, tabloul a ajuns la forma de ansamblu, fiecare nod avand cheia mai mica sau egala decat cheile fiilor sai
• Cel mai mic element al tabloului a ajuns pe post de radacina
• Interschimbam radacina cu ultimul element al tabloului, adica 1 cu 8

Calin Jebelean

Algoritmul HeapSort

12

1

2

3

5

6

4

9

7

8

Algoritmul HeapSort

​

​

​

​

​

​

​

• Elementul minim (1) se elimina si se adauga la un tablou auxiliar, initial vid, care va contine la final elementele sortate
• Acesta a fost primul pas al algoritmului de sortare HeapSort
• Vom studia inca un pas al algoritmului

Calin Jebelean

Algoritmul HeapSort

13

8

2

3

5

6

4

9

7

1

Algoritmul HeapSort

• Situatia actuala este prezentata mai jos:

Calin Jebelean

Algoritmul HeapSort

14

8

2

3

5

6

4

9

7

1

2

3

4

5

6

7

8

Index:

1

-

-

-

-

-

-

-

Tablou auxiliar:

9

-

1

Algoritmul HeapSort

​

​

​

​

​

​

​

• Nodurile neterminale considerate sunt, in ordine: 5, 3, 2 si 8
• Datorita pasului anterior, nodurile 5, 3 si 2 indeplinesc conditiile referitoare la fiii lor (pasii anteriori au usurat sarcina pasului curent)
• Nodul 8 nu indeplineste conditiile, deci va fi interschimbat cu 2

Calin Jebelean

Algoritmul HeapSort

15

8

2

3

5

6

4

9

7

Algoritmul HeapSort

​

​

​

​

​

​

​

• Nici in noua locatie, 8 nu indeplineste conditiile, ca urmare va fi interschimbat cu 5

Calin Jebelean

Algoritmul HeapSort

16

2

8

3

5

6

4

9

7

Algoritmul HeapSort

​

​

​

​

​

​

​

• Nici in noua locatie, 8 nu indeplineste conditiile, ca urmare va fi interschimbat cu 7

Calin Jebelean

Algoritmul HeapSort

17

2

5

3

8

6

4

9

7

Algoritmul HeapSort

​

​

​

​

​

​

​

• 8 nu mai are fii, deci ne oprim aici
• Tabloul a devenit ansamblu, cel mai mic element din tablou ajungand pe post de radacina
• Interschimbam radacina cu ultimul element al tabloului, adica 2 cu 8

Calin Jebelean

Algoritmul HeapSort

18

2

5

3

7

6

4

9

8

Algoritmul HeapSort

​

​

​

​

​

​

​

• Elementul minim (2) se elimina si se adauga la tabloul auxiliar
• Acesta a fost al doilea pas al algoritmului de sortare HeapSort

Calin Jebelean

Algoritmul HeapSort

19

8

5

3

7

6

4

9

2

Algoritmul HeapSort

• Situatia actuala este prezentata mai jos:

Calin Jebelean

Algoritmul HeapSort

20

8

5

3

7

6

4

9

2

1

2

3

4

5

6

7

8

Index:

1

2

-

-

-

-

-

-

Tablou auxiliar:

9

-

Algoritmul HeapSort

• Repetand algoritmul de transformare a tabloului in ansamblu si eliminand dupa fiecare pas elementul minim obtinut (radacina arborelui), vom obtine in tabloul auxiliar elementele ordonate
• La fiecare pas, tabloul scade cu un element
• De asemenea, se poate observa ca la fiecare pas, in afara de radacina arborelui, toate celelalte elemente indeplinesc deja conditia de ansamblu datorita pasului anterior
• Rezulta ca sarcina fiecarui pas nou este mult usurata de activitatea pasului/pasilor precedenti, ceea ce face ca algoritmul HeapSort sa fie foarte performant

Calin Jebelean

Algoritmul HeapSort

21

Algoritmul HeapSort

• Algoritmul HeapSort este cel mai slab algoritm de clasa O(N·log₂N)
• Este mai slab (dar nu cu mult) decat algoritmii din familia QuickSort, dar are marele avantaj fata de acestia ca nu este recursiv
• Algoritmii recursivi ruleaza rapid, dar consuma o mare cantitate de memorie, ceea ce nu le permite sa sorteze tablouri de dimensiuni oricat de mari
• HeapSort este un algoritm care “impaca” viteza cu consumul relativ mic de memorie

Calin Jebelean

Algoritmul HeapSort

22