}
==

S-a apelat caderea incepand de la al $N/2$ - lea nod, deoarece s-a aratat ca acesta este ultimul nod care mai are fii, restul fiind frunze. Sa calculam acum complexitatea acestui algoritm. Un calcul sumar ar putea spune: exista $N$ noduri, fiecare din ele se "cerne" pe $O(log N)$ nivele, deci timpul de constructie a heap-ului este $O(N log N)$. Totusi nu este asa. Presupunem ca ultimul nivel al heap-ului este plin. In acest caz, jumatate din noduri vor fi frunze si nu se vor cerne deloc. Un sfert din noduri se vor afla deasupra lor si se vor cerne cel mult un nivel. O optime din noduri se vor putea cerne cel mult doua nivele, si asa mai departe, pana ajungem la radacina care se afla singura pe nivelul ei si va putea cadea maxim h nivele (reamintim <tex> h=[\log_2 N] </tex>). Rezulta ca timpul total de calcul este dat de formula <tex> O({\sum_{k=1}^{[\log_2 N]} k} \times \frac{N}{2^{k+1}}) = O(N) </tex>. Demonstrarea egalitatii se poate face facand substitutia $N=2^h^$ si continuand calculele. Se va obtine tocmai complexitatea $O(2^h^)$. Lasam aceasta verificare ca tema cititorului.

S-a apelat caderea incepand de la al $N/2$ - lea nod, deoarece acesta este ultimul nod care mai are fii, restul cu indici mai mari fiind frunze. Sa calculam acum complexitatea acestui algoritm. Un calcul sumar ar putea spune: exista $N$ noduri, fiecare din ele se "cerne" pe $O(log N)$ nivele, deci timpul de constructie a heap-ului este $O(N log N)$. Totusi nu este asa. Presupunem ca ultimul nivel al heap-ului este plin. In acest caz, jumatate din noduri vor fi frunze si nu se vor cerne deloc. Un sfert din noduri se vor afla deasupra lor si se vor cerne cel mult un nivel. O optime din noduri se vor putea cerne cel mult doua nivele, si asa mai departe, pana ajungem la radacina care se afla singura pe nivelul ei si va putea cadea maxim h nivele (reamintim <tex> h=[\log_2 N] </tex>). Rezulta ca timpul total de calcul este dat de formula <tex> O({\sum_{k=1}^{[\log_2 N]} k} \times \frac{N}{2^{k+1}}) = O(N) </tex>. Demonstrarea egalitatii se poate face facand substitutia $N=2^h^$ si continuand calculele. Se va obtine tocmai complexitatea $O(2^h^)$. Lasam aceasta verificare ca tema cititorului.

h2(#cut). Eliminarea unui element stiind pozitia lui in heap