Sortarea cu heap

Heapsort sortează crescător construind un max-heap, apoi mutând repetat maximul de la rădăcină la sfârșitul zonei încă nesortate. Pentru $[3,1,2]$, 3 este deja la rădăcină; îl schimbăm cu ultimul element, apoi refacem heap-ul pe primele două poziții. Rezultatul final este $[1,2,3]$.

Heapsort sortează crescător în trei etape: construiește un max-heap din tablou, apoi repetă $n-1$ pași în care mută maximul (rădăcina) pe ultima poziție a zonei încă nesortate, micșorează zona heap-ului cu 1 și restabilește proprietatea heap prin coborârea noii rădăcini. Sufixul din dreapta, deja sortat, crește după fiecare extragere, iar zona heap-ului scade. Construirea pornește de la ultimul părinte, de pe poziția $[n/2]$ (indici de la 1), și coboară spre rădăcină, aplicând coborârea fiecărui nod; costă $O(n)$. Fiecare extragere costă $O(\log n)$, deci întregul algoritm costă $O(n\log n)$ în cel mai rău caz. Sortarea se face în același tablou, cu memorie auxiliară constantă, dar nu este stabilă.

Exemplul 1 — urmărirea algoritmului. Se sortează tabloul $[1,3,2,5]$, care nu este heap. Programul afișează tabloul după construire și după fiecare extragere:

#include <algorithm>
#include <iostream>
using namespace std;
void coboara(int h[], int i, int n) {
    while (2 * i <= n) {
        int f = 2 * i;
        if (f + 1 <= n && h[f + 1] > h[f]) ++f;
        if (h[i] >= h[f]) break;
        swap(h[i], h[f]);
        i = f;
    }
}
void afis(int h[], int n) {
    for (int k = 1; k <= n; ++k) cout << h[k] << " ";
    cout << "\n";
}
int main() {
    int h[] = {0, 1, 3, 2, 5}, n = 4;
    for (int i = n / 2; i >= 1; --i) coboara(h, i, n);
    afis(h, n);
    for (int m = n; m > 1; --m) {
        swap(h[1], h[m]);
        coboara(h, 1, m - 1);
        afis(h, n);
    }
}

Se afișează 5 3 2 1, 3 1 2 5, 2 1 3 5 și 1 2 3 5. La construire, părintele de pe poziția 2 (valoarea 3) are fiul 5 și se schimbă cu el: $[1,5,2,3]$; rădăcina 1 se schimbă cu 5: $[5,1,2,3]$, apoi cu 3: $[5,3,2,1]$. Prima extragere schimbă 5 cu ultimul element și coboară noua rădăcină în zona de 3 elemente: $[3,1,2|5]$. A doua schimbă 3 cu 2: $[2,1|3,5]$, iar a treia schimbă 2 cu 1: $[1|2,3,5]$. Semnul | desparte zona heap-ului de sufixul sortat.

Exemplul 2 — instabilitatea. Se sortează cheile $2_a$, $2_b$, $1$, unde indicii a și b arată ordinea inițială a cheilor egale. Tabloul $[2_a,2_b,1]$ este deja max-heap. Prima extragere schimbă rădăcina $2_a$ cu ultimul element: $[1,2_b,2_a]$, iar zona heap-ului este $[1,2_b]$. Coborârea schimbă 1 cu $2_b$: $[2_b,1|2_a]$. A doua extragere dă $[1|2_b,2_a]$. Rezultatul are cheile egale în ordinea inversă față de cea inițială ($2_b$ înaintea lui $2_a$), deci heapsort nu este stabil. Acesta este motivul pentru care, când ordinea elementelor egale contează, se alege o sortare stabilă, de exemplu prin interclasare.

Exemplul 3 — în formatul examenului. Se construiește un max-heap din tabloul $[2,7,4,9,5]$, prin coborâre începând de la ultimul părinte. Care este tabloul rezultat?

• a) $[9,7,4,2,5]$
• b) $[9,2,4,7,5]$
• c) $[2,9,4,7,5]$
• d) $[9,7,5,4,2]$

Răspunsul corect este a). Ultimul părinte este pe poziția $[5/2]=2$ (valoarea 7), cu fiii 9 și 5; se schimbă 7 cu 9: $[2,9,4,7,5]$. Rădăcina 2 are fiii 9 și 4; se schimbă cu 9: $[9,2,4,7,5]$. Valoarea 2, acum pe poziția 2, are fiii 7 și 5 și se schimbă cu 7: $[9,7,4,2,5]$. Varianta b) oprește coborârea după primul schimb al rădăcinii, c) procesează doar ultimul părinte, iar d) este tabloul sortat descrescător, care este heap, dar nu rezultatul construirii.

Cazul unui tablou deja sortat. Tabloul crescător $[1,2,3]$ nu este max-heap, pentru că rădăcina este cel mai mic element. Construirea schimbă 1 cu fiul mai mare, 3, și dă $[3,2,1]$. Prima extragere dă $[1,2|3]$, iar coborârea lui 1 produce $[2,1|3]$; a doua extragere dă $[1|2,3]$. Heapsort nu are un caz favorabil: și pe date deja sortate face aceleași $O(n\log n)$ operații.

Greșeli frecvente

• Greșit: după mutarea maximului continuăm să refacem heap-ul pe întregul tablou.
  Corect: excludem sufixul deja sortat.
• Greșit: heapsort folosește un min-heap pentru sortare crescătoare în varianta descrisă.
  Corect: folosește max-heap.
• Greșit: heapsort este garantat stabil.
  Corect: schimburile pot inversa ordinea elementelor egale.

Înainte și după