Ce este o stivă în contextul programării și ce tipuri de stive există?

Heap-ul este o zonă din memoria RAM utilizată pentru alocarea dinamică a memoriei în timpul execuției programului.

Caracteristici principale:

• Memoria este alocată și eliberată explicit de către programator (sau colectorul de gunoi).
• Nu există o secvență strictă de alocare/eliberare a blocurilor de memorie.
• Gestionarea memoriei este mai complexă decât în stivă, poate duce la fragmentare și scurgeri de memorie.

Tipuri de heap-uri (în contextul structurilor de date):

• Heap binar (Binary Heap): Arbore care satisface proprietatea heap-ului. Pentru orice nod (cu excepția rădăcinii), valoarea sa este mai mică sau mai mare decât valoarea părintelui.
  • Min Heap: Valoarea părintelui este întotdeauna mai mică sau egală cu valorile copiilor. Elementul minim se află în rădăcină.
  • Max Heap: Valoarea părintelui este întotdeauna mai mare sau egală cu valorile copiilor. Elementul maxim se află în rădăcină.
• Heap binomial (Binomial Heap): Colecție de arbori binomiali care satisfac anumite proprietăți. Suportă operații eficiente de fuziune.
• Heap Fibonacci (Fibonacci Heap): Structură de date utilizată în algoritmi precum algoritmul lui Dijkstra. Asigură timpi amortizați mai eficienți pentru anumite operații comparativ cu heap-ul binar.
• Heap de asociere (Pairing Heap): Structură de date simplă de implementat, cu timpi amortizați buni.
• Heap stâng (Leftist Heap): Structură de date care facilitează fuziunea eficientă. O proprietate importantă este "rangul" sau "lungimea drumului nul", utilizată pentru o unire rapidă.

Aceste tipuri de heap-uri sunt utilizate în diferite algoritmi, precum sortarea (Heap Sort), implementarea cozilor de prioritate, algoritmi de căutare a celui mai scurt drum etc. Alegerea unui anumit tip de heap depinde de operațiile necesare și de eficiența lor în timp.