Rozdíl mezi zásobníky a haldy

Stack vs Heap

Zásobník je uspořádaný seznam, ve kterém lze vkládat a mazat položky seznamu pouze na jednom konci zvaném vrchol. Z tohoto důvodu je zásobník považován za datovou strukturu Last in First out (LIFO). Halda je speciální struktura dat, která je založena na stromech a splňuje speciální vlastnost zvanou vlastnost haldy. Halda je také kompletní strom, což znamená, že mezi listy stromu neexistují mezery, tj. V úplném stromu je vyplněna každá úroveň před přidáním nové úrovně do stromu a uzly v dané úrovni jsou vyplněny z zleva do prava.

Co je Stack?

Jak již bylo zmíněno dříve, zásobník je datová struktura, ve které jsou prvky přidávány a odebírány pouze z jednoho konce zvaného vrchol. Zásobníky umožňují pouze dvě základní operace zvané push and pop. Operace push přidá nový prvek na vrchol zásobníku. Operace pop odstraní prvek z horní části zásobníku. Pokud je zásobník již plný, je při provádění operace push považován za přetečení zásobníku. Pokud je operace pop provedena na již prázdném zásobníku, považuje se za podtečení zásobníku. Vzhledem k malému počtu operací, které by mohly být provedeny na zásobníku, je považován za omezenou datovou strukturu. Kromě toho je podle způsobu, jak jsou definovány operace push a pop, zřejmé, že prvky, které byly přidány jako poslední do zásobníku, nejdřív vyjdou ze zásobníku. Zásobník je proto považován za datovou strukturu LIFO.

Co je Heap?

Jak již bylo zmíněno, halda je kompletní strom, který splňuje vlastnost haldy. Vlastnost haldy uvádí, že pokud y je podřízený uzel x, pak by hodnota uložená v uzlu x měla být větší nebo rovná hodnotě uložené v uzlu y (tj. Hodnota (x) ≥ hodnota (y)). Tato vlastnost znamená, že uzel s nejvyšší hodnotou by byl vždy umístěn v kořenovém adresáři. Hromada vytvořená pomocí této vlastnosti se nazývá maximální halda. Existuje další varianta vlastnosti haldy, která uvádí její opak. (tj. hodnota (x) ≤ hodnota (y)). To znamená, že uzel s nejmenší hodnotou by byl vždy umístěn v kořenovém adresáři, tzv. Min-halda. Existuje velké množství operací prováděných na halách, jako je nalezení minima (v min-haldy) nebo maximum (v max-haldy), odstranění minima (v min-haldy) nebo maxima (v max-halách), zvýšení (v max. -heaps) nebo klesající (v min-haldy) klíč, atd.

Jaký je rozdíl mezi stackem a haldy??

Hlavní rozdíl mezi zásobníky a haldy spočívá v tom, že zatímco zásobník je lineární datová struktura, halda je nelineární datová struktura. Zásobník je uspořádaný seznam, který sleduje vlastnost LIFO, zatímco halda je úplný strom, který následuje po vlastnosti haldy. Kromě toho je zásobník omezenou datovou strukturou, která podporuje pouze omezený počet operací jako push a pop, zatímco halda podporuje širokou škálu operací, jako je nalezení a odstranění minima nebo maxima, zvýšení nebo snížení klíče a sloučení.