Stack vs Heap
Zásobník je uspořádaný seznam, do kterého lze vkládat a mazat položky seznamu pouze na jednom konci zvaném 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 nazývanou vlastnost haldy. Hromada je také úplný strom, což znamená, že mezi listy stromu nejsou žádné mezery, tj. v úplném stromu je každá úroveň vyplněna před přidáním nové úrovně do stromu a uzly v dané úrovni jsou vyplněny z zleva doprava.
Co je Stack?
Jak již bylo zmíněno dříve, zásobník je datová struktura, ve které se prvky přidávají a odebírají pouze z jednoho konce, který se nazývá vrchol. 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. Operace pop odebere prvek z horní části zásobníku. Pokud je zásobník již plný, při provedení operace push se to považuje za přetečení zásobníku. Pokud je operace pop provedena 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é by mohly být provedeny na zásobníku, je považován za omezenou datovou strukturu. Navíc podle způsobu, jakým jsou definovány operace push a pop, je jasné, že prvky, které byly do zásobníku přidány jako poslední, odcházejí ze zásobníku jako první. Proto je zásobník považován za datovou strukturu LIFO.
Co je halda?
Jak již bylo zmíněno, halda je úplný strom, který splňuje vlastnost haldy. Vlastnost haldy uvádí, že pokud y je podřízeným uzlem x, pak by hodnota uložená v uzlu x měla být větší nebo rovna hodnotě uložené v uzlu y (tj. value(x) ≥ value(y)). Tato vlastnost znamená, že uzel s největší hodnotou by byl vždy umístěn v kořenu. Halda vytvořená pomocí této vlastnosti se nazývá max-heap. Existuje další varianta vlastnosti haldy, která uvádí opak tohoto. (tj. hodnota(x) ≤ hodnota(y)). To znamená, že uzel s nejmenší hodnotou by byl vždy umístěn v kořenu, tedy nazvaný min-hromada. Existuje široká škála operací prováděných s hromadami, jako je nalezení 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 max. -heaps) nebo klesající (v min-hromadách) atd.
Jaký je rozdíl mezi Stack a Heap?
Hlavní rozdíl mezi zásobníky a haldami je 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ý se řídí vlastností LIFO, zatímco halda je úplný strom, který se řídí vlastností haldy. Zásobník je navíc 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í.
