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

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

* 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

* Operatia de tipul 1: insereaza elementul $x$ in colectie
* Operatia de tipul 2: sterge elementul $NRI[x]$, unde $NRI[x]$ este al $X$-lea element intrat in colectie.
* Operatia de tipul 3: afisarea elementului minim din colectie

Se garanteaza ca nu se vor exista $2$ operatii de tipul $2$ care sa stearga acelasi element din colectie.
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 liniile $2$ .. $N+1$ se va afla descrierea operatiilor care trebuie efectuate. Primul numar, $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.

h2. Date de ieşire

h2. Explicatie

Dupa primele $3$ operatii vom in colectie elementele $4$, $7$, $9$. Astfel raspunsul la operatia de tip $3$ este $4$.

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

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 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 se va respecta proprietatea de heap.

* 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.