In cazul general, aceasta metoda de sortare necesita un spatiu de memorie
suplimentar pentru coada de prioritati, egal cu lungimea tabloului care
trebuie sortat. Daca, insa, se foloseste drept coada de prioritati un arbore
de selectie, este posibil ca toate operatiile sa se faca in tabloul initial,
fara a se cere memorie suplimentara. Se obtine astfel metoda de sortare
HeapSort.
- Figura 14 -
Fie t tabloul care trebuie sortat, de lungime n.
Intr-o prima etapa, elementele sunt extrase din tabloul t in ordinea t[1], t[2], ... t[n-1] si puse in tabloul de selectie. Daca s-au extras deja k elemente din tablou si au fost puse in arborele de selectie, atunci zona t[0],...,t[k-1] este folosita pentru tabloul de selectie, iar zona t[k],...,t[n-1] este ocupata de elementele din t ramase inca pe vechile pozitii. La sfarsitul primei etape, intregul tablou t s-a transformat in arbore de selectie.
In a doua etapa a sortarii, elementele sunt extrase pe rand din tabloul de selectie si repuse in tabloul t. La extragerea elementelor din tabloul de selectie, acestea sunt scoase in ordinea prioritatii, iar tabloul de selectie se scurteaza. In spatiul ramas liber, se pun elementele extrase: primul element extras (cel de prioritate maxima) va fi pus pe pozitia t[n-1], al doilea pe pozitia t[n-2] etc. In final, intregul tablou t contine elementele sortate in ordine crescatoare a prioritatii, iar arborele de selectie este vid.
Avand in vedere ca punerea sau extragerea unui element din tabloul de selectie are complexitatea O(log n), iar in total se pun/extrag n elemente, complexitatea sortarii prin metoda HeapSort este O(n.log n).
Exemplu: In fisierul HeapSort.java
este dat un exemplu de clasa care contine metoda statica
public static void sort(double[] t)
care sorteaza prin metoda HeapSort tabloul t cu componente de tip double.
Algoritmii folositi pentru punerea unui element in arborele de selectie
sau pentru extragerea unui element sunt aceiasi ca cei folositi in metodele
put si remove ale clasei ArboreSelectie.
Un exemplu simplu de utilizare a clasei HeapSort pentru sortarea unui tablou
este dat in fisierul TestHeapSort.java.