Heap-uri

Heapuri

h1. Heap-uri

h1. Heapuri

== include(page="template/implica-te/scrie-articole-2" user_id1="Cyber" user_id2="silviug") ==

!heapuri?delete1.JPG!

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]$ niveluri, rezulta o complexitate a procedeului de $O(log N)$.
==code(cpp) |

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]$ niveluri, de unde complexitatea logaritmica.
==code(cpp) |

void insert(Heap H, int N, int key) {

void insert(Heap H, int& N, int key) {

    H[++N] = key;
    percolate(H, N, N);
}

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

        sift(H, i, 1);

        sift(H, i - 1, 1);

    }
}
==

* 'Magnetic storms':http://acm.timus.ru/problem.aspx?space=1&num=1126
* 'Manager':http://acm.tju.edu.cn/toj/showp1675.html
* 'Supermarket':http://acm.tju.edu.cn/toj/showp1681.html

* Sea, Radu Berinde - Baraj ONI 2004
* Interclasati $K$ vectori sortati (Sugestie: complexitatea dorita este $O(N * log K)$, unde $N$ este lungimea sirului rezultat prin interclasare).
* Determinati cele mai mici $K$ elemente dintr-un sir cu $N$ elemente cand dispuneti de memorie mult mai putina ca $O(N)$ ({$K$} este mult mai mic decat $N$).

* Sea - Baraj ONI 2004 (Autor: Radu Berinde)
* Interclasati $K$ vectori sortati. (Sugestie: complexitatea dorita este $O(N * log K)$, unde $N$ este lungimea sirului rezultat prin interclasare)
* Determinati cele mai mici $K$ elemente dintr-un sir cu $N$ elemente cand dispuneti de memorie mult mai putina ca $O(N)$. ({$K$} este mult mai mic decat $N$)
 

3528