![](images/title/creareaunuiheap.jpg)
O prima solutie este de a insera
succesiv elementele in heap plecand initial de la heap-ul format
dintr-un singur element:
void CreareHeap()
{
int i;
for (i=0; i<n; i++)
InsertHeap(i,H[i]);
}
|
Analizand complexitatea procedurii
de inserare deducem ca, in cazul cel mai defavorabil, valoarea
nou inserata urca pana in radacina arborelui, deci necesita
O(h) operatii elementare, unde h este inaltimea heap-ului. Un
heap fiind un arbore binar complet, inaltimea sa h va fi [log
n], deci inserarea unui nod intr-un heap cu n elemente este
de O(log n).
Sa estimam complexitatea in cazul
cel mai defavorabil a procedurii de constructie a heap-ului
prin inserari succesive. Daca toate cele 2^i valori de pe nivelul
i urca pana in radacina, obtinem complexitate de O(n log n).
O strategie mai eficienta de constructie
a unui heap se bazeaza pe ideea de echilibrare. Apelul procedurii
InsertHeap(n,x) poate fi interpretat ca o combinare de doua
heap-uri: un heap cu n elemente si un heap format numai din
elementul x. Putem construi heap-ul cu radacina H[i] combinand
la fiecare pas doua heap-uri cu dimensiuni apropiate, heap-ul
cu radacina 2i, heap-ul cu radacina 2i+1 si cu elementul H[i];
void CreareHeap()
{
int i;
for (i=(n-1)/2; i>=0; i--)
CombHeap(i,n);
} |
Complexitatea algoritmului
Notam h = [log n] inaltimea heap-ului. Pentru fiecare nod x
de pe nivelul i, i = 0->h-1, pentru a construi heap-ul cu
radacina x se fac cel mult h-i coborari a valorii x in arbore.
Deci, in cazul cel mai defavorabil numarul de operatii elementare
efectuate de algoritm pentru a construi un heap cu n elemente
este O(n). Algoritmul de constructie a unui heap a devenit astfel
liniar.
|