Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-12-26 18:59:59.
Revizia anterioară   Revizia următoare  

Heap-uri

Acest articol a fost adăugat de cyberClaudia Cardei cyber
Intră aici dacă doreşti să scrii articole sau află cum te poţi implica în celelalte proiecte infoarena!

(Categoria Structuri de date, Autor Catalin Francu, Versiunea originala preluata din cartea "Psihologia concursurilor de informatica")

In acest articol prezentam structura de date numita heap, cum poate fi aceasta implementata precum si unele implementari STL. Desi este putin probabil sa ajungeti sa implementati heap-urile de la "zero" daca stiti STL, consideram ca prezentarea acestora nu este de prisos. Aici atingem problema mai generala a "de ce trebuie sa inteleg X (poate fi vorba de un algoritm, o structura de date, s.a.m.d.) daca il am deja implementat?" Iata cateva motive:

  • va antreneaza mintea
  • va veti putea descurca in situatii in care aveti nevoie de o structura de date similara dar nu la fel
  • veti fi utilizatori informati ai bibliotecii STL
  • veti intelege cand este bine sa folosoti o structura de date si cand nu
  • veti avea avantajul de a sti precis de ce operatiile au anumite complexitati

Acum ca avem o motivatie, sa studiem impreuna heap-urile.

Definirea notiunii de heap

Un heap (engl. gramada) este un vector care poate fi privit si ca un arbore binar, asa cum se vede in figura de mai jos:

Langa fiecare nod din arbore se afla cate un numar, reprezentand pozitia in vector pe care ar avea-o nodul respectiv. Pentru cazul considerat, vectorul echivalent ar fi H = (12 10 11 10 7 9 3 2 8 1 4 3).

Se observa ca nodurile sunt parcurse de la stanga la dreapta si de sus in jos. O proprietate necesara pentru ca un arbore binar sa se poata numi heap este ca toate nivelele sa fie complete, cu exceptia ultimului, care se completeaza incepand de la stanga si continuand pana la un punct. De aici deducem ca inaltimea unui heap cu N noduri este  h=[\log_2 N] (reamintim ca inaltimea unui arbore este adancimea maxima a unui nod, considerand radacina drept nodul de adancime 0). Reciproc, numarul de noduri ale unui heap de inaltime h este  N\in [2^h, 2^{h+1}-1].

Tot din aceasta organizare mai putem deduce ca tatal unui nod k > 1 este nodul [k/2], iar fiii nodului k sunt nodurile 2k si 2k+1. Daca 2k = N, atunci nodul 2k+1 nu exista, iar nodul k are un singur fiu; daca 2k > N, atunci nodul k este frunza si nu are nici un fiu. Exemple: tatal nodului 5 este nodul 2, iar fiii sai sunt nodurile 10 si 11. Tatal nodului 6 este nodul 3, iar unicul sau fiu este nodul 12. Tatal nodului 9 este nodul 4, iar fii nu are, fiind frunza in heap.

Dar cea mai importanta proprietate a heap-ului, cea care il face util in operatiile de aflarea a maximului, este aceea ca valoarea oricarui nod este mai mare sau egala cu valoarea oricarui fiu al sau. Dupa cum se vede mai sus, nodul 2 are valoarea 10, iar fiii sai - nodurile 4 si 5 - au valorile 10 si respectiv 7. Intrucat operatorul ≥ este tranzitiv, putem trage concluzia ca un nod este mai mare sau egal decat oricare din nepotii sai si, generalizand, va rezulta ca orice nod este mai mare sau egal decat toate nodurile din subarborele a carui radacina este el.

Aceasta afirmatie nu decide in nici un fel intre valorile a doua noduri dispuse astfel incat nici unul nu este descendent al celuilalt. Cu alte cuvinte, nu inseamna ca orice nod de pe un nivel mic are valoare mai mare decat nodurile mai apropiate de frunze. Este cazul nodului 7, care are valoarea 3 si este mai mic decat nodul 9 de valoare 8, care este totusi asezat ma jos in heap. In orice caz, o prima concluzie care rezulta din aceasta proprietate este ca radacina are cea mai mare valoare din tot heap-ul.

Structura de heap permite efectuarea multor operatii intr-un timp foarte bun:

  • Cautarea maximului in O(1)
  • Crearea unei structuri de heap dintr-un vector oarecare in O(N)
  • Eliminarea unui element in O(log N)
  • Inserarea unui element in O(log N)
  • Sortarea elementelor din heap in O(N log N)
  • Cautarea unui element (singura care nu este prea eficienta) in O(N).

Desigur, toate aceste operatii se fac mentinand permanent structura de heap a arborelui, adica respectand modul de repartizare a nodurilor pe nivele si inaltarea elementelor de valoare mai mare. Este de la sine inteles ca datele nu se vor reprezenta in memorie in forma arborescenta, ci in cea vectoriala.

Precizam de asemenea ca heap-ul poate fi organizat pe baza operatorului de . In acest caz, in varful heap-ului vom avea minimul dintre elementele pastrate in heap. In functie de operatia folosita, putem numi structura de date max-heap sau min-heap. In continuare vom prezenta operatiile intr-un max-heap, adaptarea lor pentru min-heap-uri fiind usoara.

Structura de heap si metode ajutatoare

In blocul de cod de mai jos prezentam cum se defineste un heap ca vector si cateva metode ajutatoare:

const int MAX_HEAP_SIZE = 16 * 1024;
typedef int Heap[MAX_HEAP_SIZE];

inline int father(int nod) {
    return nod / 2;
}

inline int left_son(int nod) {
    return nod * 2;
}

inline int right_son(int nod) {
    return nod * 2 + 1;
}

Cautarea maximului

Practic operatia aceasta nu are de facut decat sa intoarca valoarea primului element din vector:
inline int max(Heap H) {
    return H[1];
}

Crearea unei structuri de heap dintr-un vector oarecare

Pentru a discuta acest aspect, vom vorbi mai intai despre doua proceduri specifice heap-urilor, sift (engl. a cerne) si percolate (engl. a se infiltra). Sa presupunem ca un vector are o structura de heap, cu exceptia unui nod care este mai mic decat unul din fiii sai. Este cazul nodului 3 din figura de mai jos, care are o valoare mai mica decat nodul 6:

Ce e de facut ? Desigur, nodul va trebui coborat in arbore, iar in locul lui vom aduce alt nod, mai exact unul dintre fiii sai. Intrebarea este: care din fiii sai ? Daca vom aduce nodul 7 in locul lui, acesta fiind mai mic decat nodul 6, inegalitatea se va pastra. Trebuie deci sa schimbam nodul 3 cu nodul 6:

Problema nu este insa rezolvata, deoarece noul nod 6, proaspat "retrogradat", este inca mai mic decat fiul sau, nodul 12. De data aceasta avem un singur fiu, deci o singura optiune: schimbam nodul 6 cu nodul 12 si obtinem o structura de heap corecta:

Procedura sift primeste ca parametri un heap H cu N noduri si un nod K si presupune ca ambii subarbori ai nodului K au structura de heap corecta. Misiunea ei este sa "cearna" nodul K pana la locul potrivit, interschimband mereu nodul cu cel mai mare fiu al sau pana cand nodul nu mai are fii (ajunge pe ultimul nivel in arbore) sau pana cand fiii sai au valori mai mici decat el.

void sift(Heap H, int N, int K) {
    int son;
    do {
        son = 0;
        // Alege un fiu mai mare ca tatal.
        if (left_son(K) <= N) {
            son = left_son(K);
            if (right_son(K) <= N && H[right_son(K)] > H[left_son(K)]) {
                son = right_son(K);
            }
            if (H[son] <= H[K]) {
                son = 0;
            }
        }

        if (son) {
            swap(H[K], H[son]);  // Functie STL ce interschimba H[K] cu H[son].
            K = son;
        }
    } while (son);
}

Procedura percolate se va ocupa tocmai de fenomenul invers. Sa presupunem ca un heap are o "defectiune" in sensul ca observam un nod care are o valoare mai mare decat tatal sau. Atunci, va trebui sa interschimbam cele doua noduri. Este cazul nodului 10 din figura care urmeaza. Deoarece fiul care trebuie urcat este mai mare ca tatal, care la randul lui (presupunand ca restul heap-ului e corect) este mai mare decat celalalt fiu al sau, rezulta ca dupa interschimbare fiul devenit tata este mai mare decat ambii sai fii. Trebuie totusi sa privim din nou in sus si sa continuam sa urcam nodul in arbore fie pana ajungem la radacina, fie pana ii gasim un tata mai mare ca el. Iata ce se intampla cu nodul 10:

void percolate(Heap H, int N, int K) {
    int key = H[K];

    while ((K > 1) && (key > H[father(K)])) {
        H[K] = H[father(K)];
        K = father(K);
    }

    H[K] = key;
}

Acum ne putem ocupa efectiv de construirea unui heap. Am spus ca procedura sift presupune ca ambii fii ai nodului pentru care este ea apelata au structura de heap. Aceasta inseamna ca putem apela procedura sift pentru orice nod imediat superior nivelului frunzelor, deoarece frunzele sunt arbori cu un singru nod, si deci heap-uri corecte. Apeland procedura sift pentru toate nodurile de deasupra frunzelor, vom obtine deja o structura mai organizata, asigurandu-ne ca pe ultimele doua nivele avem de-a face numai cu heap-uri. Apoi apelam aceeasi procedura pentru nodurile de pe al treilea nivel incepand de la frunze, apoi pentru cele de deasupra lor si asa mai departe pana ajungem la radacina. In acest moment, heap-ul este construit. Iata cum functioneaza algoritmul pentru un arbore total dezorganizat:

Nivelul frunzelor este organizat

Ultimele doua nivele sunt organizate

Ultimele trei nivele sunt organizate

Structura de heap

void build_heap(Heap H, int N) {
    for (int i = N/2; i > 0; --i) {
        sift(H, N, i);
    }
}

S-a apelat caderea incepand de la al N/2 - lea nod, deoarece s-a aratat ca acesta este ultimul nod care mai are fii, restul fiind frunze. Sa calculam acum complexitatea acestui algoritm. Un calcul sumar ar putea spune: exista N noduri, fiecare din ele se "cerne" pe O(log N) nivele, deci timpul de constructie a heap-ului este O(N log N). Totusi nu este asa. Presupunem ca ultimul nivel al heap-ului este plin. In acest caz, jumatate din noduri vor fi frunze si nu se vor cerne deloc. Un sfert din noduri se vor afla deasupra lor si se vor cerne cel mult un nivel. O optime din noduri se vor putea cerne cel mult doua nivele, si asa mai departe, pana ajungem la radacina care se afla singura pe nivelul ei si va putea cadea maxim h nivele (reamintim  h=[\log_2 N] ). Rezulta ca timpul total de calcul este dat de formula  O({\sum_{k=1}^{[\log_2 N]} k} \times \frac{N}{2^{k+1}}) = O(N) . Demonstrarea egalitatii se poate face facand substitutia N=2h si continuand calculele. Se va obtine tocmai complexitatea O(2h). Lasam aceasta verificare ca tema cititorului.

Eliminarea unui element stiind pozitia lui in heap

Daca eliminam un element din heap, trebuie numai sa refacem structura de heap. In locul nodului eliminat s-a creat un gol, pe care trebuie sa il umplem cu un alt nod. Care ar putea fi acela? Intrucat trebuie ca toate nivelele sa fie complet ocupate, cu exceptia ultimului, care poate fi gol numai in partea sa dreapta, rezulta ca singurul nod pe care il putem pune in locul celui eliminat este ultimul din heap. Odata ce l-am pus in gaura facuta, trebuie sa ne asiguram ca acest nod "de umplutura" nu strica proprietatea de heap. Deci vom verifica: daca nodul pus in loc este mai mare ca tatal sau, vom apela procedura percolate. Altfel vom apela procedura sift, in eventualitatea ca nodul este mai mic decat unul din fiii sai. Iata exemplul de mai jos:

Sa presupunem ca vrem sa eliminam nodul de valoare 9, aducand in locul lui nodul de valoare X. Insa X poate fi orice numar mai mic sau egal cu 18. Spre exemplu, X poate fi 16, caz in care va trebui urcat deasupra nodului de valoare 10, sau poate fi 1, caz in care va trebui cernut pana la nivelul frunzelor. Deoarece caderea si urcarea se pot face pe cel mult (log N) nivele, rezulta o complexitate a procedeului de O(log N).

void cut(Heap H, int& N, int K) {
    H[K] = H[N];
    --N;

    if ((K > 1) && (H[K] > H[father(K)])) {
        percolate(H, N, K);
    } else {
        sift(H, N, K);
    }
}

Inserarea unui element

Daca vrem sa inseram un nou element in heap, lucrurile sunt mult mai simple. Nu avem decat sa-l asezam pe a N+1-a pozitie in vector si apoi sa-l "promovam" pana la locul potrivit. Din nou, urcarea se poate face pe maxim (log N) nivele, de unde complexitatea logaritmica.

void insert(Heap H, int N, int key) {
    H[++N] = key;
    percolate(H, N, N);
}

Sortarea unui vector (heapsort)

Acum, ca am stabilit toate aceste lucruri, ideea algoritmului de sortare vine de la sine. Incepem prin a construi un heap. Apoi extragem maximul (adica varful heap-ului) si refacem heap-ul. Cele doua operatii luate la un loc dureaza O(1)+O(log N) = O(log N). Apoi extragem din nou maximul, (care va fi al doilea element ca marime din vector) si refacem din nou heap-ul. Din nou, complexitatea operatiei compuse este O(log N). Daca facem acest lucru de N ori, vom obtine vectorul sortat intr-o complexitate de O(N log N).

Partea cea mai frumoasa a acestui algoritm, la prima vedere destul de mare consumator de memorie, este ca el nu foloseste deloc memorie suplimentara. Iata explicatia: cand heap-ul are N elemente, vom extrage maximul si il vom tine minte undeva in memorie. Pe de alta parte, in locul maximului (adica in radacina arborelui) trebuie adus ultimul element al vectorului, adica H[N]. Dupa aceasta operatie, heap-ul va avea N-1 noduri, al N-lea ramanand liber. Ce alt loc mai inspirat decat acest al N-lea nod ne-am putea dori pentru a stoca maximul? Practic, am interschimbat radacina, adica pe H1 cu H[N]. Acelasi lucru se face la fiecare pas, tinand cont de micsorarea permanenta a heap-ului.

void heap_sort(Heap H, int N) {
    build_heap(H, N);

    // Sorteaza vectorul.
    for (int i = N; i >= 2; --i) {
        swap(H[1], H[i]);
        sift(H, i, 1);
    }
}

Cautarea unui element

Aceasta operatie este singura care nu poate fi optimizata (in sensul reducerii complexitatii sub O(N)). Aceasta deoarece putem fi siguri ca un nod mai mic este descendentul unuia mai mare, dar nu putem sti daca se afla in subarborele stang sau drept; din aceasta cauza, nu putem face o cautare binara. Totusi, o oarecare imbunatatire se poate aduce fata de cautarea secventiala. Daca radacina unui subarbore este mai mica decat valoarea cautata de noi, cu atat mai mult putem fi convinsi ca descendentii radacinii vor fi si mai mici, deci putem sa renuntam la a cauta acea valoare in tot subarborele. In felul acesta, se poate intampla ca bucati mari din heap sa nu mai fie explorate inutil. Pe cazul cel mai defavorabil, insa, parcurgerea intregului heap este necesara. Lasam scrierea unei proceduri de cautare pe seama cititorului.

STL

TODO: HEAP-uri implementate de mana VS priority_queue<> VS set<>

Desi nu sunt greu de implementat, avem vesti bune pentru programatorii in C++. In STL, cozile de prioritate (adica max-heap-urile) sunt deja implementate. Totusi, mentionam ca priority_queue nu este in standard-ul STL, aceasta inseamnand ca nu vor fi gasite neaparat in toate implementarile STL. Desi asta reprezinta un risc (e posibil sa nu gasitit priority_queue pe calculatoarele de la concurs) acesta esta minin.

O alternativa la priority_queue-uri sunt set-urile si multiset-urile din STL. Acestea au doua avantaje: sunt in standard STL (deci nu riscati nimic) si pot efectua si cautari in O(logN) fiindca sunt implementate ca arbori binari echilibrati. Totusi avantajele vin cu un cost: set-urile si multiset-urile pot fi mai incete decat cozile de prioritate.

Daca nu sunteti familiari cu aceste structuri de date, va recomandam sa cititi paginile lor de documentatie: priority_queue<>, set<> si multiset. Daca nu intelegeti chiar tot de la inceput (pentru ca nu stiti clase si template-uri in C++), uitati-va pe exemple si pe lista de functii membre si invatati cum se folosesc.

In continuare vom ilustra cum putem implementa operatiile de extragere a maximului, extragere a minimului, inserare, stergere si cautare folosind un multi_set. Vom folosi un multiset pentru ca toate copiile unui numar vor fi pastrate daca el va fi inserat de mai multe ori (spre deosebire de set, care il va pastra o singura data).

Aplicatii

  • Dijkstra cu heap-uri
    (codul sursa:)
  • Magnetic storms - timus, 1126
  • Sea (Berinde), Baraj ONI 2004 TODO: Pus pe infoareana, fortat o structura de date care intretine dinamic evenimentele (de exemplu heap) prin micsorarea limitei de memorie.
  • Pe astea le-am rezolvat cu set-uri, nu stiu daca merge si cu heap-uri ca au nevoie si de stergere in log(N) -- smenul de la Dijkstra?:

TODO: Prezentam sau nu problema de mai jos?

PRO:

  • E interesanta si este o aplicatie a heapurilor

CONTRA:

  • Este o aplicatie teoretica/fortata
  • Mareste prea mult articolul

Feedback (Stefan): As sugera transformarea problemei intr-una mai utila si mai putin fortata: Sa se interclaseze in mod eficient K vectori sortati.

Feedback (Cosmin): Merge problema, zic ca trebuie bagata, eventual daca e prea artificiala o punem ultima. E misto problema lui Stefan, alta problema ar fi sa se determine cele mai mici k elemente dintr-un sir de lungime n daca ai memorie << O(n). In cod ar trebui schimbate siftarile cu 1 cu inmultiri si impartiri cu 2, si pare mai putin exoteric codul. Alta chestie, am putea numi articolul cozi de prioritati si sa mentionam heapuri interclasabile, sau cozi de prioritati cand costurile sunt mici. Am putea sa bagam observatiile cu celelalte cozi de prioritati ca si in Cormen intr-o sectiune la sfarsitul articolului cu extinderi.

Exemple vreicat mai multe sa dai,pt calumea crede ca heapurile folosesc numai la heap sort si e bine sa schimbam ideea asta. Parerea mea e ca orice concept nou trebuie explicat cu 3 exemple care nu sunt inrudite ca sa il intelegi k lumea.

Daca articolul e prea lung ar fimisto sa avem ceva butoane care expandeaza bucati din articol, sau celputin un cuprins la inceput, daca te intereseaza implementarea sau aplicatiile sa poti sari rapid la ce te intereseaza.

Problema

Sperand ca am reusit sa explicam modul de functionare al unui heap, .

Un vector se numeste k-sortat daca orice element al sau se gaseste la o distanta cel mult egala cu k de locul care i s-ar cuveni in vectorul sortat. Iata un exemplu de vector 2-sortat cu 5 elemente:

V=(6 2 7 4 10)
Vsortat =(2 4 6 7 10)

Se observa ca elementele 4 si 6 se afla la doua pozitii distanta de locul lor in vectorul sortat, elementele 2 si 7 se afla la o pozitie distanta, iar elementul 10 se afla chiar pe pozitia corecta. Distanta maxima este 2, deci vectorul V este 2-sortat. Desigur, un vector k-sortat este in acelasi timp si un vector (k+1)-sortat, si un vector (k+2)-sortat etc., deoarece, daca orice element se afla la o distanta mai mica sau egala cu k de locul potrivit, cu atat mai mult el se va afla la o distanta mai mica sau egala cu k+1, k+2 etc. In continuare, cand vom spune ca vectorul este k-sortat, ne vom referi la cel mai mic k pentru care afirmatia este adevarata. Prin urmare, un vector cu N elemente poate fi N-1 sortat in cazul cel mai defavorabil. Mai facem precizarea ca un vector 0-sortat este un vector sortat in intelesul obisnuit al cuvantului, deoarece fiecare element se afla la o distanta egala cu 0 de locul sau.

Problema este: dandu-se un vector k-sortat cu N elemente numere intregi, se cere sa-l sortam intr-un timp mai bun decat O(N*log N).

Date sunt citite din fisierul input.txt care contine pe prima linie valorile lui N si K (2 ≤ K < N ≤ 10000), despartite printr-un spatiu. Pe a doua linie se dau cele N elemente ale vectorului, despartite prin spatii. In fisierul output.txt se vor tipari pe o singura linie elementele vectorului sortat, separate prin spatii.

Iata un exemplu:

input.txtoutput.txt
5
6 2 7 4 10
2 4 6 7 10

Ne propunem obtinerea unei complexitati O(N*logK). Evident, putem sorta vectorul fara sa tinem cont de propietatile sale dar am obtine o complexitate O(N*logN). Diferentierea intre aceasta solutie si cea prezentata in continuare este probabil imposibil de facut in regim de concurs. Prezentam totusi solutia O(N*logK) de amorul artei si pentru a ilustra conceptual heapurile :)

Rezolvare

Chiar faptul ca ni se cere o complexitate de ordinul O(N*log k) ne sugereaza construirea unui heap cu O(k) noduri. Sa ne inchipuim ca am construi un heap H format din primele k+1 elemente ale vectorului V. Diferenta fata de ce am spus pana acum este ca orice nod va trebui sa fie mai mic decat fiii sai. Acest heap va servi deci la extragerea minimului.

Deoarece vectorul este k-sortat, rezulta ca elementul care s-ar gasi pe prima pozitie in vectorul sortat se poate afla in vectorul nesortat pe oricare din pozitiile 1, 2, ..., k+1. El se afla asadar in heap-ul H; in plus, fiind cel mai mic, stim exact de unde sa-l luam: din varful heap-ului. Deci vom elimina acest element din heap si il vom trece "undeva" separat (vom vedea mai tarziu unde). In loc sa punem in locul lui ultimul element din heap, insa, vom aduce al k+2-lea element din vector si il vom lasa sa se cearna. Acum putem fi siguri ca al doilea element ca valoare in vectorul sortat se afla in heap, deoarece el se putea afla in vectorul nesortat undeva pe pozitiile 1, 2, ..., k+2, toate aceste elemente figurand in heap (bineinteles ca minimul deja extras se exclude din discutie). Putem sa mergem la sigur, luand al doilea minim direct din varful heap-ului.

Vom proceda la fel pana cand toate elementele vectorului vor fi adaugate in heap. Din acel moment vom continua sa extragem din varful heap-ului, revenind la vechea modalitate de a umple locul ramas gol cu ultimul nod disponibil. Continuam si cu acest procedeu pana cand heap-ul se goleste. In acest moment am obtinut vectorul sortat "undeva" in memorie. De fapt, daca ne gandim putin, vom constata ca, odata ce primele k+1 elemente din vector au fost trecute in heap, ordinea lor in vectorul V nu mai conteaza, ele putand servi chiar la stocarea minimelor gasite pe parcurs. Pe masura ce aceste locuri se vor umple, altele noi se vor crea prin trecerea altor elemente in heap. Iata deci cum nici acest algoritm nu necesita memorie suplimentara.