Diferența dintre stack și heap

Stack vs Heap

Stack este o listă ordonată în care inserarea și ștergerea elementelor din listă se poate face numai într-un capăt numit top. Din acest motiv, stiva este considerată ca o structură de date Last in First out (LIFO). Heap este o structură de date specială care se bazează pe copaci și satisface o proprietate specială numită proprietatea heap. De asemenea, o grămadă este un arbore complet, ceea ce înseamnă că nu există decalaje între frunzele arborelui, adică într-un copac complet, fiecare nivel fiind umplut înainte de a adăuga un nou nivel copacului și nodurile dintr-un anumit nivel sunt umplute 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 top. Stivele permit doar două operații fundamentale numite push and pop. Operația de împingere adaugă un element nou în partea superioară a teancului. Operația pop elimină un element din partea de sus a stivei. Dacă stack-ul este deja plin, atunci când se efectuează o operație de împingere, este considerată ca o suprapunere de stive. Dacă se efectuează o operație pop pe o stivă deja goală, este considerată ca o sub-flux de stivă. Datorită numărului mic de operațiuni care ar putea fi efectuate pe un teanc, este considerată o structură de date restricționată. În plus, în funcție de modul în care sunt definite operațiile push și pop, este clar că elementele care au fost adăugate ultima în teanc ies din primul set. Prin urmare, stiva este considerată o structură de date LIFO.

Ce este Heap?

După cum am menționat mai devreme, mormanul este un copac complet care satisface proprietatea heap. În cazul în care y este un nod copil de 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ă. O grămadă construită folosind această proprietate este numită max-heap. Există o altă variație a proprietății de heap care afirmă inversul acestei situații. (adică valoarea (x) ≤ valoarea (y)). Aceasta implică faptul că nodul cu cea mai mică valoare ar fi întotdeauna plasat la rădăcină, numit astfel un heap min. Există o gamă largă de operații efectuate pe grămezi, cum ar fi găsirea unui minim (în min-heaps) sau a unui maxim (în heaps max), ștergerea minimă (în min-heaps) sau maximă (în max-heaps) -saupe) sau scăderea (în min-grămezi) a cheii, etc.

Care este diferența dintre Stack și Heap?

Principala diferență între stive și grămezi este că, în timp ce stiva este o structură liniară de date, heapul este o structură de date neliniare. Stack este o listă ordonată care urmează proprietății LIFO, în timp ce heapul este un arbore complet care urmează proprietatea heap. În plus, stiva este o structură de date restricționată care acceptă doar un număr limitat de operații ca push și pop, în timp ce heapul suportă o gamă largă de operații, cum ar fi găsirea și ștergerea minime sau maxime, creșterea sau scăderea cheii și fuzionarea.