== 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:

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: se insereaza elementul $x$ in colectie
* Operatia de tipul 2: se sterge elementul intrat al $x$-lea in colectie in ordine cronologica
* Operatia de tipul 3: se afiseaza elementul minim 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 urmatoarele $N$ linii, se va afla descrierea operatiilor care trebuie efectuate. Primul numar, $cod$, reprezinta tipul operatiei. 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 in ordinea data.

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
* Se garanteaza ca nu se vor exista $2$ operatii de tipul $2$ care sa stearga acelasi element din colectie.

* 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

h2. Explicatie

Dupa primele $3$ operatii vom avea 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 $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 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 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.
 
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.

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

$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:

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:
* 'Base3':problema/base3

* 'Catun':problema/catun
* 'Lupul urias si rau':problema/lupu
* 'Timbre':problema/timbre

3512