| 4
|

h3. Explicatie

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

h3. Indicatii de rezolvare

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.

*Nota* La fiecare operatie trebuie sa avem grija sa actualizam pozitiile elementelor.

Puteti citi "aici":http://infoarena.ro/heapuri mai multe detalii.

Un articol interesant care descrie foarte bine operatiile suportate de un heap se afla "aici":http://infoarena.ro/heapuri.

h3. Probleme suplimentare

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:

* "Djikstra":http://infoarena.ro/problema/dijkstra

* "Catun":http://infoarena.ro/problema/catun

* "Arbore partial de cost minim":http://infoarena.ro/problema/apm

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