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: 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.
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 care urmeaza a fi efectuata. 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.
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
Exemplu
| heapuri.in | heapuri.out |
|---|---|
| 9 1 4 1 7 1 9 3 1 2 2 1 3 2 4 3 | 4 |
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 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.
Rezolvarea optima bazeaza pe folosirea unui heap, care suporta aceste efectuarea operatiilor de tipul 1 si 2 in O(log N) si a operatiilor de tipul 3 in O(1).
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. Evident raspunsul la operatiile de tip 3 se va gasi in radacina arborelui.
O implementare usoara este aceea de a reprezenta heapul ca pe un vector. Astfel radacina se va afla pe pozitia 1 iar pentru un nod i, fii lui se vor afla pe pozitiile 2*i respectiv 2*i+1.
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 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.
Un articol interesant care descrie foarte bine operatiile suportate de un heap se afla aici.
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 sau algoritmul lui Prim. Alte probleme interesante care folosesc heapuri ar fi:
