Ce este o grămadă?

Un heap este o structură de date specială în formă de arbore care satisface proprietatea heap-ului. Această proprietate afirmă că pentru orice vârf, cu excepția rădăcinii, valoarea cheii acestuia trebuie să fie într-o anumită relație cu valoarea cheii părintelui său. Există două tipuri principale de heap-uri:

• Max-heap: Valoarea cheii fiecărui vârf nu este mai mică decât valorile cheilor copiilor săi. Elementul maxim se află în rădăcină.
• Min-heap: Valoarea cheii fiecărui vârf nu este mai mare decât valorile cheilor copiilor săi. Elementul minim se află în rădăcină.

Heap-ul este de obicei implementat ca un array, ceea ce permite accesul eficient la elemente și efectuarea operațiilor. Relația dintre părinți și copii în array este următoarea:

• Pentru un element cu indicele i (începând de la 0), copilul stâng se află la indicele 2i + 1.
• Copilul drept se află la indicele 2i + 2.
• Părintele se află la indicele floor((i - 1) / 2).

Operațiile principale pe heap:

• Insert (Inserare): Adăugarea unui element nou. Timp de execuție O(log n), unde n este numărul de elemente.
• Extract-Max / Extract-Min: Eliminarea și returnarea elementului maxim (în max-heap) sau minim (în min-heap). Timp de execuție O(log n).
• Heapify (Construirea heap-ului): Transformarea unui array arbitrar într-un heap. Timp de execuție O(n).

Heap-urile sunt utilizate în algoritmi de sortare (de exemplu, sortarea prin heap), în cozi de prioritate și în algoritmi de căutare a celor mai scurte drumuri (de exemplu, algoritmul lui Dijkstra).