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 elementul intrat al x-lea in colectie in ordine cronologica
- Operatia de tipul 3: se afiseaza elementul minim din colectie
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.
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 determinarea arborelui partial de cost minim. Alte probleme ce pot fi rezolvate folosind heap-uri sunt:
