Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | heapuri.in, heapuri.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Savin Tiberiu •devilkind |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Heapuri
Se da o colectie de numere naturale initial vida. Se cere sa se efectueze N operatii asupra acestei multimi, astfel:
- Operatia de tipul 1: se insereaza elementul x in colectie
- Operatia de tipul 2: se sterge al x-lea element intrat in colectie in ordine cronologica
- Operatia de tipul 3: se afiseaza elementului minim din colectie
Date de intrare
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. Daca cod este 1 sau 2, atunci se va mai citi si numarul x, avand semnificatia din enunt.
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.
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.
Exemplu
| heapuri.in | heapuri.out |
|---|---|
| 9 1 4 1 7 1 9 3 1 2 2 1 3 2 4 3 | 4 2 7 |
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.
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, 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.
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 si algoritmul lui Prim pentru APM. Alte probleme ce pot fi rezolvate folosind heap-uri sunt:
