Pagini recente » Sandbox | Diferente pentru utilizator/test.php intre reviziile 67 si 123 | Diferente pentru utilizator/siminescu_cristina intre reviziile 2 si 3 | Istoria paginii utilizator/pod_psd | Diferente pentru heapuri intre reviziile 14 si 15
Diferente pentru
heapuri intre reviziile
#14 si
#15
Nu exista diferente intre titluri.
Diferente intre continut:
h2. Cautarea unui element
Aceasta operatie este singura care nu poate fi optimizata (in sensul reducerii complexitatii sub $O(N)$). Aceasta deoarece putem fi siguri ca un nod mai mic este descendentul unuia mai mare, dar nu putem sti daca se afla in subarborele stang sau drept; din aceasta cauza, nu putem face o cautare binara. Totusi, o oarecare imbunatatire se poate aduce fata de cautarea secventiala. Daca radacina unui subarbore este mai mica decat valoarea cautata de noi, cu atat mai mult putem fi convinsi ca descendentii radacinii vor fi si mai mici, deci putem sa renuntam la a cauta acea valoare in tot subarborele. In felul acesta, se poate intampla ca bucati mari din heap sa nu mai fie explorate inutil. Pe cazul cel mai defavorabil, insa, parcurgerea intregului heap este necesara. Lasam scrierea unei proceduri de cautare pe seama cititorului.
****
Sperand ca am reusit sa explicam modul de functionare al unui heap, sa incercam sa rezolvam si problema propusa. Chiar faptul ca ni se cere o complexitate de ordinul $O(N*log k)$ ne sugereaza construirea unui heap cu $O(k)$ noduri. Sa ne inchipuim ca am construi un heap $H$ format din primele $k+1$ elemente ale vectorului $V$. Diferenta fata de ce am spus pana acum este ca orice nod va trebui sa fie mai mic decat fiii sai. Acest heap va servi deci la extragerea minimului.
Deoarece vectorul este $k-sortat$, rezulta ca elementul care s-ar gasi pe prima pozitie in vectorul sortat se poate afla in vectorul nesortat pe oricare din pozitiile 1, 2, ..., $k+1$. El se afla asadar in heap-ul $H$; in plus, fiind cel mai mic, stim exact de unde sa-l luam: din varful heap-ului. Deci vom elimina acest element din heap si il vom trece "undeva" separat (vom vedea mai tarziu unde). In loc sa punem in locul lui ultimul element din heap, insa, vom aduce al $k+2$-lea element din vector si il vom lasa sa se cearna. Acum putem fi siguri ca al doilea element ca valoare in vectorul sortat se afla in heap, deoarece el se putea afla in vectorul nesortat undeva pe pozitiile 1, 2, ..., $k+2$, toate aceste elemente figurand in heap (bineinteles ca minimul deja extras se exclude din discutie). Putem sa mergem la sigur, luand al doilea minim direct din varful heap-ului.
Vom proceda la fel pana cand toate elementele vectorului vor fi adaugate in heap. Din acel moment vom continua sa extragem din varful heap-ului, revenind la vechea modalitate de a umple locul ramas gol cu ultimul nod disponibil. Continuam si cu acest procedeu pana cand heap-ul se goleste. In acest moment am obtinut vectorul sortat "undeva" in memorie. De fapt, daca ne gandim putin, vom constata ca, odata ce primele $k+1$ elemente din vector au fost trecute in heap, ordinea lor in vectorul $V$ nu mai conteaza, ele putand servi chiar la stocarea minimelor gasite pe parcurs. Pe masura ce aceste locuri se vor umple, altele noi se vor crea prin trecerea altor elemente in heap. Iata deci cum nici acest algoritm nu necesita memorie suplimentara.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.