Problema este: dandu-se un vector k-sortat cu N elemente numere intregi, se cere sa-l sortam intr-un timp mai bun decat O(N log N).
Intrarea: Fisierul INPUT.TXT contine pe prima linie valorile lui N si K (2 � K < N si N � 10000), despartite printr-un spatiu. Pe a doua linie se dau cele N elemente ale vectorului, despartite prin spatii.
Intrarea: Fisierul INPUT.TXT contine pe prima linie valorile lui N si K (2 � K < N si N � 10000), despartite printr-un spatiu. Pe a doua linie se dau cele N elemente ale vectorului, despartite prin spatii.
Iesirea: In fisierul OUTPUT.TXT se vor tipari pe o singura linie elementele vectorului sortat, separate prin spatii.
Tot din aceasta organizare mai putem deduce ca tatal unui nod k>1 este nodul �k/2�, iar fiii nodului k sunt nodurile 2k si 2k+1. Daca 2k=N, atunci nodul 2k+1 nu exista, iar nodul k are un singur fiu; daca 2k>N, atunci nodul k este frunza si nu are nici un fiu. Exemple: tatal nodului 5 este nodul 2, iar fiii sai sunt nodurile 10 si 11. Tatal nodului 6 este nodul 3, iar unicul sau fiu este nodul 12. Tatal nodului 9 este nodul 4, iar fii nu are, fiind frunza in heap.
Tot din aceasta organizare mai putem deduce ca tatal unui nod k>1 este nodul �k/2�, iar fiii nodului k sunt nodurile 2k si 2k+1. Daca 2k=N, atunci nodul 2k+1 nu exista, iar nodul k are un singur fiu; daca 2k>N, atunci nodul k este frunza si nu are nici un fiu. Exemple: tatal nodului 5 este nodul 2, iar fiii sai sunt nodurile 10 si 11. Tatal nodului 6 este nodul 3, iar unicul sau fiu este nodul 12. Tatal nodului 9 este nodul 4, iar fii nu are, fiind frunza in heap.
Dar cea mai importanta proprietate a heap-ului, cea care il face util in operatiile de cautare, este aceea ca valoarea oricarui nod este mai mare sau egala cu valoarea oricarui fiu al sau. Dupa cum se vede mai sus, nodul 2 are valoarea 10, iar fiii sai - nodurile 4 si 5 - au valorile 10 si respectiv 7. Intrucat operatorul ��� este tranzitiv, putem trage concluzia ca un nod este mai mare sau egal decat oricare din nepotii sai si, generalizand, va rezulta ca orice nod este mai mare sau egal decat toate nodurile din subarborele a carui radacina este el.
Dar cea mai importanta proprietate a heap-ului, cea care il face util in operatiile de cautare, este aceea ca valoarea oricarui nod este mai mare sau egala cu valoarea oricarui fiu al sau. Dupa cum se vede mai sus, nodul 2 are valoarea 10, iar fiii sai - nodurile 4 si 5 - au valorile 10 si respectiv 7. Intrucat operatorul ��� este tranzitiv, putem trage concluzia ca un nod este mai mare sau egal decat oricare din nepotii sai si, generalizand, va rezulta ca orice nod este mai mare sau egal decat toate nodurile din subarborele a carui radacina este el.
Aceasta afirmatie nu decide in nici un fel intre valorile a doua noduri dispuse astfel incat nici unul nu este descendent al celuilalt. Cu alte cuvinte, nu inseamna ca orice nod de pe un nivel mic are valoare mai mare decat nodurile mai apropiate de frunze. Este cazul nodului 7, care are valoarea 3 si este mai mic decat nodul 9 de valoare 8, care este totusi asezat ma jos in heap. In orice caz, o prima concluzie care rezulta din aceasta proprietate este ca radacina are cea mai mare valoare din tot heap-ul.
Structura de heap permite efectuarea multor operatii intr-un timp foarte bun:
� Cautarea maximului in O(1);
� Crearea unei structuri de heap dintr-un vector oarecare in O(N);
� Eliminarea unui element in O(log N);
� Inserarea unui element in O(log N);
� Sortarea in O(N log N)
� Cautarea (singura care nu este prea eficienta) in O(N).
* Cautarea maximului in O(1);
* Crearea unei structuri de heap dintr-un vector oarecare in O(N);
* Eliminarea unui element in O(log N);
* Inserarea unui element in O(log N);
* Sortarea in O(N log N)
* Cautarea (singura care nu este prea eficienta) in O(N).
Desigur, toate aceste operatii se fac mentinand permanent structura de heap a arborelui, adica respectand modul de repartizare a nodurilor pe nivele si �inaltarea� elementelor de valoare mai mare. Este de la sine inteles ca datele nu se vor reprezenta in memorie in forma arborescenta, ci in cea vectoriala. Sa le analizam pe rand.
Desigur, toate aceste operatii se fac mentinand permanent structura de heap a arborelui, adica respectand modul de repartizare a nodurilor pe nivele si inaltarea elementelor de valoare mai mare. Este de la sine inteles ca datele nu se vor reprezenta in memorie in forma arborescenta, ci in cea vectoriala. Sa le analizam pe rand.
