Stack vs Heap
Stack je seřazený seznam, do kterého lze vkládat a mazat položky seznamu pouze na jednom konci, který se nazývá horní. Z tohoto důvodu je zásobník považován za datovou strukturu Last in First Out (LIFO). Halda je speciální datová struktura, 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 nejsou žádné 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 to Stack?
Jak již bylo zmíněno dříve, stack je datová struktura, ve které jsou prvky přidávány a odebírány pouze z jednoho konce zvaného horní část. Zásobníky umožňují pouze dvě základní operace zvané push a pop. Operace push přidá nový prvek do horní části zásobníku. Pop operace 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 se popová operace provádí na již prázdném zásobníku, považuje se to za podtečení zásobníku. Vzhledem k malému počtu operací, které lze na zásobníku provést, je považován za omezenou datovou strukturu. Kromě toho je podle způsobu, jakým jsou definovány operace push a pop, jasné, že prvky, které byly přidány jako poslední do zásobníku, nejdříve vyjdou ze zásobníku. Zásobník je proto považován za datovou strukturu LIFO.
Co je halda?
Jak již bylo zmíněno dříve, halda je kompletní strom, který splňuje vlastnost haldy. Vlastnost haldy uvádí, že pokud je y podřízený uzel x, pak by hodnota uložená v uzlu x měla být větší nebo rovna hodnotě uložené v uzlu y (tj. Hodnota (x) ≥ hodnota (y)). Tato vlastnost znamená, že uzel s největší hodnotou by byl vždy umístěn v kořenovém adresáři. Halda vytvořená pomocí této vlastnosti se nazývá maximální halda. Existuje další variace vlastnosti haldy, která udává opak toho. (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, což se nazývá min-halda. Existuje celá řada operací prováděných na hromadách, jako je hledání minima (v minimálních hromadách) nebo maxima (v maximálních hromadách), mazání minima (v minimálních hromadách) nebo maxima (v maximálních hromadách),zvýšení (v maximálních hromadách) nebo snížení (v minimálních hromadách) klíče atd.
Jaký je rozdíl mezi Stack a Heap?
Hlavní rozdíl mezi hromadami a hromadami spočívá v tom, že zatímco zásobník je lineární datová struktura, halda je nelineární datová struktura. Stack je seřazený seznam, který následuje po vlastnosti LIFO, zatímco halda je úplný strom, který následuje po vlastnosti haldy. Zásobník je dále omezená datová struktura, 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í.
