Aplicatii cu heap-uri

Apărut la 1 iulie 2010 în Teste de informatică   |   autor: Dan Pracsiu 0 comentarii

Aplicaţie cu heap-uri

Se consideră şirul iniţial de numere 1, 2, ..., n (n £ 10.000) memorat într-un vector H. Asupra acestui şir se efectuează operaţii de două tipuri:
- add: adăugarea unei valori întregi x la valoarea de la poziţia i (adică H[i] = H[i] + x)
- querry: care este valoarea minimă din vectorul H?

În fişierul querry.in pe prima linie se află două numere naturale n şi M (1 £ M £ 1.000.000), iar pe următoarele M linii se găseşte codificată câte o operaţie. Operaţia add se codifică prin tripletul 1 i x, iar operaţia querry prin numărul 2. Pentru fiecare operaţie querry trebuie să afişaţi în fişierul querry.out pe câte o linie care este valoarea minimă din vector.

Exemplu

Indicaţie: organizând vectorul ca un min-heap, fiecare operaţie add se va efectua în timp O(log n) (pentru reorganizarea min-heap-ului), iar operaţia de interogare se va efectua în O(1) (minimul se va găsi mereu în H[1]). Este necesar un al doilea vector în care se va memora poziţia fiecărei valori din heap.

Număr de accesări: 3842

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică