== include(page="template/taskheader" task_id="heapuri") ==

Se da o colectie de numere naturale initial vida. Se cere sa se efectueze $N$ operatii asupra acestei multimi astfel. Operatiile sunt de $3$ tipuri:

Fie o multime de numere naturale initial vida. Se cere sa se efectueze $N$ operatii asupra acestei multimi, unde operatiile sunt de tipul celor de mai jos:

* Operatia de tipul 1: inserareaza elementul $x$ in colectie
* Operatia de tipul 2: stergere elementul $NRI[x]$, unde $NRI[x]$ este al $X$-lea element intrat in colectie (in ordine cronologica).
* Operatia de tipul 3: care este elementul minim din colectie
 
Se garanteaza ca nu se vor exista $2$ operatii de tipul $2$ care sa stearga acelasi element din colectie.

* operatia de tipul {$1$}: se insereaza elementul $x$ in multime
* operatia de tipul {$2$}: se sterge elementul intrat al $x$-lea in multime, in ordine cronologica
* operatia de tipul {$3$}: se afiseaza elementul minim din multime

h2. Date de intrare

Fisierul de intrare $heapuri.in$ va contine pe prima linie numarul $N$. Pe liniile $2$ .. $N+1$ se va afla un numar $cod$. $Cod$ reprezinta tipul operatiei care urmeaza a fi efectuata. Daca $cod$ este $1$ sau $2$ atunci se va mai citi si numarul $x$ avand semnificatia din enunt.

Fisierul de intrare $heapuri.in$ va contine pe prima linie numarul $N$. Pe urmatoarele $N$ linii se va afla descrierea operatiilor care trebuie efectuate. Primul numar de pe fiecare linie, $cod$, reprezinta tipul operatiei. Daca $cod$ este $1$ sau $2$, atunci linia corespunzatoare va mai contine si numarul $x$, avand semnificatia din enunt.

h2. Date de ieşire

Fisierul de iesire $heapuri.out$ va contine pe cate o linie raspunsul pentru fiecare operatie de tipul $3$ din fisierul de intrare.

Fisierul de iesire $heapuri.out$ va contine, pe cate o linie, raspunsul pentru fiecare operatie de tipul $3$ din fisierul de intrare, in ordinea data.

h2. Restricţii
* $1 ≤ N ≤ 200 000$

* Elementele colectiei nu vor depasi $1 000 000 000$
* Se garanteaza ca nu se va cere niciodata sa se afle minimul daca colectia este vida

* Elementele multimii nu vor depasi $1 000 000 000$
* Se garanteaza ca nu se va cere niciodata sa se afle minimul daca multimea este vida
* Se garanteaza ca nu vor exista $2$ operatii de tipul $2$ care sa stearga acelasi element din multime
* Pentru o operatie de tipul $2$ se va sterge un element care e deja intrat in multime

h2. Exemplu

2 4
3
| 4

2
7

|
h2. Explicatie

Dupa primele $3$ operatii vom in colectie elementele $4$, $7$, $9$. Astfel raspunsul la operatia de tip $3$ este $4$.
In continuare vom adauga elementul $2$ si vom sterge primul element inserat, adica $4$, ramanand cu elementele $2$, $7$, $9$.
Vom sterge apoi al $4$-lea element intrat, adica $2$, in colectia aflandu-se la sfarsit numai $7$ si $9$, minimul fiind $7$.

Dupa primele $3$ operatii vom avea in multime elementele $4$, $7$ si $9$. Astfel raspunsul la operatia de tip $3$ este $4$. In continuare vom adauga elementul $2$ si vom sterge primul element inserat, adica $4$, ramanand cu elementele $2$, $7$ si $9$. Vom sterge apoi al $4$-lea element intrat, adica $2$, in multime aflandu-se la sfarsit numai $7$ si $9$, minimul fiind $7$.

h2. Indicatii de rezolvare

Problema se poate rezolva brut-force tinand numerele intrun vector, si efectuand pur si simplu fiecare operatie. Aceasta solutie are complexitate $O(1)$ pe o operatie de tipul $1$ si $O(N)$ pe celelalte si nu ar trebui sa ia $~30$ de puncte.
 
Rezolvarea optima bazeaza pe folosirea unui heap, care suporta aceste efectuarea operatiilor de tipul $1$ si $2$ in $O(log N)$ si a operatiilor de tipul $3$ in $O(1)$.
Un heap este un arbore binar, cu proprietatea ca fiecare nod, are asociata o cheie, cheie care este mica decat cheile asociate nodurilor din subarborele sau. Evident raspunsul la operatiile de tip $3$ se va gasi in radacina arborelui.
O implementare usoara este aceea de a reprezenta heapul ca pe un vector. Astfel radacina se va afla pe pozitia $1$ iar pentru un nod $i$, fii lui se vor afla pe pozitiile $2*i$ respectiv $2*i+1$.
Cand vrem sa inseram un element nou in vector, il adaugam la capatul sirului, si apoi il interschimbam cu parintele sau pana cand se respecta proprietatea de heap.
De asemenea pentru fiecare element vom tine minte pozitia pe care se afla acesta in vector. Astfel ca atunci cand o sa vrem sa stergem un element din heap, il interschibam cu ultimul element din vector si scadem dimensiunea acestuia cu $1$. Totusi acest lucru ne poate strica proprietatea de heap. Astfel avem $2$ cazuri:
 
* Elementul nostru este mai mic decat parintele sau, caz in care aplicam acelasi algoritm pe care il aplicam si atunci cand vrem sa adaugam un nod in heap, adica il interschibam cu parintele sau pana cand acesta va fi mai mare decat parintele sau.
* Elementul nostru este mai mare decat fii sai, caz in care vom continua sa il interschimbam cu cel mai mic fiu al sau pana cand acesta va fi mai mare decat ambii sai fii.
 
*Nota* La fiecare operatie trebuie sa avem grija sa actualizam pozitiile elementelor.
 
Un articol interesant care descrie foarte bine operatiile suportate de un heap se afla "aici":http://infoarena.ro/heapuri.

Problema se poate rezolva prin metoda $brute-force$, tinand numerele intr-un vector si efectuand fiecare operatie fara nici un rafinament. Aceasta solutie are complexitate $O(1)$ pe o operatie de tipul $1$ si $O(N)$ pe celelalte. O astfel de abordare nu ar trebui sa ia mai mult de $30$ de puncte.
Rezolvarea optima foloseste o structura de date cunoscuta sub numele de _heap_, care suporta efectuarea operatiilor de tipul $1$ si $2$ in complexitate timp $O(log{~2~}N)$ si a operatiilor de tipul $3$ in timp constant.
Un heap este un arbore binar, cu proprietatea ca fiecare nod are asociata o cheie, cheie care este mai mica decat cheile asociate nodurilor din subarborele sau. Astfel, raspunsul la o operatie de tip $3$ se va gasi in radacina arborelui. Pentru a intelege modul in care functioneaza aceasta structura de date va recomandam sa cititi 'acest articol':heapuri, ce contine si cateva desene demonstrative. Un alt articol care prezinta acest subiect sa gaseste {'aici':http://en.wikipedia.org/wiki/Heap_(data_structure)}.
Pentru a putea implementa mai usor aceasta structura, se recomanda reprezentarea heap-ului ca un vector. Astfel radacina se va afla pe pozitia $1$, iar pentru un nod $i$, parintele sau se va afla pe pozitia $i/2$, in timp ce fii lui se vor afla pe pozitiile $2*i$ si, respectiv, $2*i+1$. De asemenea, va fi necesar sa pastram un vector cu pozitia fiecarui nod in heap, pentru a-l putea localiza rapid in cazul unei operatii de stergere. O implementare ce obtine $100$ de puncte se gaseste 'aici':job_detail/235474?action=view-source.

h2. Aplicatii

Heapurile sunt utile in general din cauza faptului ca putem executa rapid cu ajutorul lor operatiile descrise mai sus. Aceste operatii sunt in general utile atunci cand vrem sa implementam algoritmi clasici cum ar fi "agloritmul lui Djikstra":http://infoarena.ro/problema/dijkstra sau "algoritmul lui Prim":http://infoarena.ro/problema/apm. Alte probleme interesante care folosesc heapuri ar fi:
 
* "Catun":http://infoarena.ro/problema/catun

Heap-urile sunt niste structuri de date foarte utile, deoarece operatiile descrise mai sus sunt intalnite intr-o multime de situatii. Doua aplicatii clasice ce folosesc aceasta structura de date sunt 'algoritmul lui Dijkstra':problema/dijkstra si algoritmul lui Prim pentru determinarea 'arborelui partial de cost minim':problema/apm. Alte probleme ce pot fi rezolvate folosind heap-uri sunt:

== include(page="template/taskfooter" task_id="heapuri") ==

* 'Base3':problema/base3
* 'Catun':problema/catun
* 'Lupul urias si rau':problema/lupu
* 'Timbre':problema/timbre
* 'Barbar':problema/barbar
* "Sarov zones":http://acm.sgu.ru/problem.php?contest=0&problem=171
* 'Mine':problema/mine

*Paul*:
Baga mai multe probleme suplimentare / aplicatii. Explica in ce alte situatii e bun un heap (ex. Dijkstra, Prim). Uita-te cum au facut altii: 'bfs':problema/bfs, 'trie':problema/trie, 'inversmodular':problema/inversmodular.
*Cosmin*:
De ce e multime si nu colectie de elemente. Nu imi place ca adaugi o restrictie care nu e necesara la heapuri prin faptul ca zici ca elementele apartin unei multimi.
*devil*
@cosmin: Cand am zis multime ma gandeam mai mult la faptul ca intr-o multime nu poate exista acelasi element de 2 ori, si astfel atunci cand sterg un element e clar ce se intampla. Am uitat insa acest lucru pe parcurs si am uitat sa precizez ca daca un element e deja in heap nu mai intra inca o data si de asemenea am uitat sa pun elementele mai mici ca 1 000 000 ca sa se poate verifica usor acest lucru.
@paul
1. o sa bag un test cu 40000 de inserturi si 40000 de operatii de stergere a minimului si restul queryuri.
2. O sa bag o sursa si sa vad cum fac un test mare.
3. Ma gandeam sa las articolu ala, dar ok explic
4. Caut acuma

== include(page="template/taskfooter" task_id="heapuri") ==

3512