Stiva vs Heap
Stack este o listă ordonată în care inserarea și ștergerea elementelor din listă se poate face doar într-un capăt numit partea de sus. Din acest motiv, stiva este considerată ca o structură de date Last in First out (LIFO). Heap este o structură specială de date care se bazează pe arbori și satisface o proprietate specială numită proprietate heap. De asemenea, o grămadă este un copac complet, ceea ce înseamnă că nu există goluri între frunzele copacului, adică într-un copac complet fiecare nivel este completat înainte de a adăuga un nou nivel la copac, iar nodurile dintr-un anumit nivel sunt completate din de la stânga la dreapta.
Ce este Stack?
Așa cum am menționat mai devreme, stiva este o structură de date în care elementele sunt adăugate și eliminate dintr-un singur capăt numit partea de sus. Stivele permit doar două operațiuni fundamentale numite push și pop. Operația de împingere adaugă un nou element în partea de sus a stivei. Operația pop elimină un element din partea de sus a stivei. Dacă stiva este deja plină, atunci când se efectuează o operație de împingere, aceasta este considerată o supraîncărcare a stivei. Dacă o operațiune pop este efectuată pe o stivă deja goală, este considerată ca o stivă sub depășire. Datorită numărului mic de operațiuni care ar putea fi efectuate pe o stivă, aceasta este considerată o structură de date restrânsă. În plus, conform modului în care sunt definite operațiunile push și pop, este clar că elementele care au fost adăugate ultimele în stivă ies mai întâi din stivă. Prin urmare, stiva este considerată o structură de date LIFO.
Ce este Heap?
Așa cum am menționat mai devreme, heap este un arbore complet care satisface proprietatea heap. Proprietatea Heap afirmă că, dacă y este un nod copil al lui x, atunci valoarea stocată în nodul x ar trebui să fie mai mare sau egală cu valoarea stocată în nodul y (adică valoarea(x) ≥ valoarea(y)). Această proprietate implică faptul că nodul cu cea mai mare valoare ar fi întotdeauna plasat la rădăcină. Un heap construit folosind această proprietate se numește max-heap. Există o altă variație a proprietății heap care afirmă inversul acesteia. (adică valoarea(x) ≤ valoarea(y)). Acest lucru implică faptul că nodul cu cea mai mică valoare ar fi întotdeauna plasat la rădăcină, denumit astfel min-heap. Există o gamă largă de operațiuni efectuate pe heaps, cum ar fi găsirea minimului (în min-heaps) sau maxim (în max-heaps), ștergerea minimului (în min-heaps) sau maxim (în max-heaps), creșterea (în max-heaps). -heaps) sau descrescătoare (în min-heaps) etc.
Care este diferența dintre Stack și Heap?
Principala diferență dintre stive și heaps este că, în timp ce stiva este o structură de date liniară, heap-ul este o structură de date neliniară. Stiva este o listă ordonată care urmează proprietatea LIFO, în timp ce heap-ul este un arbore complet care urmează proprietatea heap. În plus, stack este o structură de date restrânsă care acceptă doar un număr limitat de operațiuni, cum ar fi push și pop, în timp ce heap acceptă o gamă largă de operațiuni, cum ar fi găsirea și ștergerea minimului sau maximului, creșterea sau scăderea cheii și îmbinarea.
