Heap

Un max-heap este un arbore binar aproape complet în care valoarea fiecărui părinte este cel puțin la fel de mare ca valorile fiilor. Rădăcina este maximul întregii structuri. Vectorul $[9,5,7]$ reprezintă un max-heap: 9 este rădăcina, iar 5 și 7 sunt fiii ei. Vectorul nu trebuie să fie sortat.

Un max-heap este un arbore binar aproape complet în care valoarea fiecărui nod este cel puțin la fel de mare ca valorile fiilor lui; într-un min-heap relația este inversă. Arborele se memorează într-un vector. Cu indici de la 1, fiii nodului de pe poziția $i$ sunt pe $2i$ și $2i+1$, iar tatăl pe $[i/2]$; cu indici de la 0, formulele devin $2i+1$, $2i+2$ și $[(i-1)/2]$. Vectorul nu este sortat: doar relațiile părinte–fii sunt impuse. Rădăcina este maximul întregii structuri și se citește în $O(1)$. Înălțimea arborelui este proporțională cu $\log n$, deci inserarea și extragerea maximului cer $O(\log n)$ pași.

Exemplul 1 — inserarea. Noua valoare se pune pe prima poziție liberă, la capătul vectorului, apoi urcă: cât timp este mai mare decât tatăl, se schimbă cu el. Se inserează 10 în max-heap-ul $[9,5,7]$:

#include <algorithm>
#include <iostream>
using namespace std;
int main() {
    int h[10] = {0, 9, 5, 7}, n = 3;
    h[++n] = 10;
    int i = n;
    while (i > 1 && h[i / 2] < h[i]) {
        swap(h[i], h[i / 2]);
        i /= 2;
    }
    for (int k = 1; k <= n; ++k) cout << h[k] << " ";
}

Se afișează 10 9 7 5. Valoarea 10 ajunge pe poziția 4, fiul lui 5 (poziția 2); se schimbă cu 5, apoi, pe poziția 2, cu 9 (poziția 1). Heap-ul devine $[10,9,7,5]$. Cele două schimburi au fost suficiente pentru că înălțimea este 2; numărul schimburilor nu depășește înălțimea. Dacă valoarea inserată ar fi fost 4, ea ar fi rămas pe poziția 4, fără nicio schimbare.

Exemplul 2 — extragerea maximului. Ultima valoare înlocuiește rădăcina, iar dimensiunea scade cu 1. Noua rădăcină coboară: se schimbă cu cel mai mare dintre fii cât timp este mai mică decât acesta. Din $[10,9,7,5]$ se extrage maximul:

#include <algorithm>
#include <iostream>
using namespace std;
int main() {
    int h[10] = {0, 10, 9, 7, 5}, n = 4;
    int maxim = h[1];
    h[1] = h[n--];
    int i = 1;
    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;
    }
    cout << maxim << ":";
    for (int k = 1; k <= n; ++k) cout << " " << h[k];
}

Se afișează 10: 9 5 7. Valoarea 5 din ultima poziție devine rădăcină, apoi se compară cu fiii 9 și 7; se alege fiul mai mare, 9, și se face schimbul. Heap-ul rămas este $[9,5,7]$, adică exact cel de la început. Dacă 5 ar fi fost schimbat cu fiul mai mic, 7, rădăcina 7 ar fi fost mai mică decât fiul 9 și proprietatea heap s-ar fi pierdut. La coborâre, numărul schimburilor nu depășește înălțimea: pentru cele $n=3$ elemente rămase este cel mult $[{\log }_{2}3]=1$, și exact un schimb s-a făcut.

Exemplul 3 — în formatul examenului. Max-heap-ul $[20,15,18,10,12,9]$ primește valoarea 19. Care este vectorul rezultat?

• a) $[20,15,19,10,12,9,18]$
• b) $[20,15,18,10,12,9,19]$
• c) $[20,15,19,10,12,18,9]$
• d) $[20,19,18,10,12,9,15]$

Răspunsul corect este a). Valoarea 19 se pune pe poziția 7, al cărei tată este poziția $[7/2]=3$, cu valoarea 18. Cum $19>18$, se schimbă. Pe poziția 3, tatăl este poziția 1, cu valoarea 20, iar $19<20$, deci urcarea se oprește. Varianta b) lasă 19 pe poziția 7 și nu restabilește proprietatea heap. Varianta c) este tot un heap valid, dar nu rezultatul urcării: valorile 9 și 18 și-au schimbat poziția fără motiv. Varianta d) calculează greșit tatăl poziției 7 ca poziția 2, nu 3.

Greșeli frecvente

• Greșit: toate valorile unui max-heap sunt sortate în vector.
  Corect: doar relațiile părinte–fii sunt impuse.
• Greșit: rădăcina unui max-heap este minimul.
  Corect: este maximul.
• Greșit: după inserarea lui 10 în exemplu, acesta rămâne obligatoriu la sfârșit.
  Corect: urcă până la rădăcină.

Înainte și după