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.