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 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)}.

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