În cazul general, această metodă de sortare necesită un spațiu de
memorie suplimentar pentru coada de priorităti, egal cu lungimea
tabloului care trebuie sortat. Dacă, însă, se folosește drept coadă de
priorități un arbore de selecție, este posibil ca toate operațiile să
se facă în tabloul inițial, fără a se cere memorie suplimentară. Se
obține astfel metoda de sortare HeapSort.
- Figura 14 -
Fie t tabloul care trebuie sortat, de lungime n.
Într-o prima etapă, elementele sunt extrase din tabloul t in ordinea t[1], t[2], ... t[n-1] și puse în tabloul de selecție. Dacă s-au extras deja k elemente din tablou și au fost puse în arborele de selectie, atunci zona t[0],...,t[k-1] este folosită pentru tabloul de selecție, iar zona t[k],...,t[n-1] este ocupată de elementele din t ramase încă pe vechile poziții. La sfârșitul primei etape, întregul tablou t s-a transformat în arbore de selectie.
În a doua etapă a sortării, elementele sunt extrase pe rând din tabloul de selecție și repuse în tabloul t. La extragerea elementelor din tabloul de selecție, acestea sunt scoase în ordinea priorității, iar tabloul de selecție se scurtează. În spațiul rămas liber, se pun elementele extrase: primul element extras (cel de prioritate maximă) va fi pus pe pozitia t[n-1], al doilea pe pozitia t[n-2] etc. În final, întregul tablou t conține elementele sortate în ordine crescătoare a priorității, iar arborele de selecție este vid.
Având în vedere că punerea sau extragerea unui element din tabloul de selecție are complexitatea O(log n), iar in total se pun/extrag n elemente, complexitatea sortării prin metoda HeapSort este O(n.log n).
Exemplu: În fișierul HeapSort.java
este dat un exemplu de clasă care conține metoda statică
public static void sort(double[] t)
care sortează prin metoda HeapSort tabloul t cu componente de tip
double. Algoritmii folosiți pentru punerea unui element în arborele de
selecție sau pentru extragerea unui element sunt aceiași ca cei
folosiți în metodele put și remove ale clasei ArboreSelectie. Un exemplu simplu de
utilizare a clasei HeapSort pentru sortarea unui tablou este dat în
fișierul TestHeapSort.java.