Crearea unui Min-Heap

O primă soluție este de a insera succesiv elementele in heap plecând inițial de la heap-ul format dintr-un singur element:

  void CreareHeap()
  {
    int i;
    for (i=0; i<n; i++)
        inserare(H,i,H[i]);
  }

Analizând complexitatea procedurii de inserare deducem că, în cazul cel mai nefavorabil, valoarea nou inserată urcă până în rădăcina arborelui, deci necesită O(h) operații elementare, unde h este înălțimea heap-ului. Un heap fiind un arbore binar complet, înălțimea sa h va fi [log n], deci inserarea unui nod într-un heap cu n elemente este de
O(log n).

Să estimăm complexitatea în cazul cel mai nefavorabil a procedurii de construcție a heap-ului prin inserări succesive. Dacă toate cele 2^i valori de pe nivelul i urcă până în rădăcină, obținem complexitate de O(n log n).

Notiuni Introductive

Generator Heap

Heap

Coadă cu prioritate

Aplicații

Dicționar

O strategie mai eficientă de construcție a unui heap se bazează pe ideea de echilibrare. Apelul procedurii inserare(H,n,x) poate fi interpretat ca o combinare de două heap-uri: un heap cu n elemente și un heap format numai din elementul x. Putem construi heap-ul cu rădăcina H[i] combinând la fiecare pas doua heap-uri cu dimensiuni apropiate, heap-ul cu rădăcina 2*i, heap-ul cu rădăcina 2*i+1 și cu elementul H[i];

  void CreareHeap()
  {
    int i;
    for (i=(n-1)/2; i>=0; i--)
            CombHeap(i, n);
  }

Complexitatea algoritmului

Notăm h = [log n] înălțimea heap-ului. Pentru fiecare nod x de pe nivelul i, i = 0->h-1, pentru a construi heap-ul cu rădăcina x se fac cel mult h-i coborâri a valorii x în arbore. Deci, în cazul cel mai nefavorabil numărul de operații elementare efectuate de algoritm pentru a construi un heap cu n elemente este O(n). Algoritmul de construcție a unui heap a devenit astfel liniar.