Datové struktury (obsah)

Hodnoty uložené v binární haldě (min-heap) Binární halda (binary heap) je úplný binární strom, ve kterém platí, že každý potomek vrcholku má nižší nebo stejnou hodnotu nežli vrcholek sám. V případě, že není poslední hladina haldy zaplněna, jsou uzly ukládány do haldy zleva. Další důležitou vlastností je, že pokud indexujeme (od čísla 1) prvky haldy od shora dolů, zleva doprava, pak potomci každého vr...

Binomiální halda Binomiální halda (Binomial heap) je halda složená z lesa binomiálních stromů. Každý prvek každého stromu má vyšší prioritu, než kterýkoliv z jeho potomků – halda se proto chová jako prioritní fronta. Binomiální halda má oproti binární a d-regulární haldě výhodu v rychlejších operacích sloučení hald () a vložení prvku (amortizovaně ). Binomiální strom Binonomiální strom řádu 0 obsahuje prá...

Datová struktura disjoint-set slouží k vytvoření systému navzájem se nepřekrývajících podmnožin. Pro implementaci se používají dvě základní operace - Union (spojení dvou podmnožin v jednu) a Find (nalezení reprezentanta daného prvku). Sloučením názvů těchto operací vzniká označení pro implementaci této datové struktury - Union-Find problém/Union-Find algoritmus. Motivace Union-Find problém nalézá uplatnění při řešení otázky, zda-li jsou dva uz...

D-regulární halda D-regulární halda je n-ární úplný strom (zaplňovaný zleva doprava), ve kterém platí, že každý předek má nižší hodnotu (prioritu) než všichni jeho potomci. Tento typ uspořádání haldy se nazývá min heap, v případě opačného uspořádání hovoříme o max heap. Speciálním případem d-regulární haldy pro je binární halda. D-regulární halda funguje díky svým vlastnostem jako prioritní fronta. ...

Dynamické pole (Vector, ArrayList) je datový kontejner (struktura určená k uchovávání dat) postavený nad polem. Dynamické pole umožňuje přidávat libovolný počet prvků, čímž eliminuje hlavní nevýhodu klasického pole – fixní velikost. Princip Dynamické pole ukládá své prvky do vnitřního pole fixní délky, v okamžiku, kdy je kapacita pole vyčerpána, dojde k alokaci nového většího pole (obvykle 2x většího z důvodu amortizace), všechny prvky původní...

Fronta je jedním ze základních datových typů a slouží k ukládání a výběru dat takovým způsobem, aby prvek, který byl uložen jako první, byl také jako první vybrán. Tomuto principu se říká FIFO - first in, fist out. Opačný přístup - LIFO - last in, first out - používá datový typ zásobník. Speciálním případem fronty je tzv. prioritní fronta, ve které mohou prvky s vyšší prioritou předbíhat na výstupu ty s nižší prioritou. Typické operace ...

Graf K5 Grafem nazýváme uspořádanou trojici uzlů, hran a incidencí. Zobrazení incidence přiřazuje dvojici uzlů právě jednu hranu. Neorientovaný graf V případě, kdy incidence přiřazuje hraně neuspořádanou dvojici uzlů, nazýváme graf neorientovaným grafem. Neorientovaný graf, který neobsahuje rovnoběžné hrany, nazýváme prostým grafem, v opačném případě multigrafem. V případě neexistence smyček (hra...

Hashovací tabulka (hash table, rozptýlená tabulka, hešovací tabulka) je datová struktura, která slouží k ukládání dvojic klíč-hodnota. Hashovací tabulka kombinuje výhody vyhledávání pomocí indexu (složitost ) a procházení seznamu (nízké nároky na paměť). Možnosti ukládání dvojic klíč-hodnota Pole Uvažujme, že chceme ukládat dvojice klíč-hodnota a vyhledávat v nich. Jednou z možností by pak bylo jako klíč zvolit celé číslo (nebo nějaké mapo...

Kruhový buffer (Circular buffer) je implementací fronty (FIFO) nad polem, která se používá především jako vyrovnávací paměť datových tocích. Princip Kruhový buffer se skládá z pole fixní délky a dvou ukazatelů. První z ukazatelů míří na první obsazený prvek, druhý na první volné místo v poli. V okamžiku, kdy je do bufferu přidán nový prvek, tak se druhý ukazatel zinkrementuje, v případě odstranění prvního prvku fronty dojde k inkrementaci prv...

Množina Množina (set) je abstraktní datová struktura, která obsahuje hodnoty, aniž by garatovala jejich pořadí. Jelikož se jedná se o implementaci matematického termínu množina, tak tato struktura obsahuje každý prvek vždy maximálně jednou. Podobnou strukturou, která však smí obsahovat daný prvek vícekrát, je multimnožina. Pro implementaci systému navzájem se nepřekrývajících podmnožin používáme dat...

Multimnožina Multimnožina (multiset, množina s opakováním, bag) je datový typ vycházející z množiny. Multimnožina slouží jako kontejner na entity, jenž negarantuje pořadí uložených prvků, a který může obsahovat jednotlivé prvky (hodnoty) vícekrát. Implementace Nejjednodušším způsobem implementace je použít list a zapomenout na pořadí. Tento způsob je ovšem velmi neefektivní z hlediska použit...

Spojový seznam (Lineární seznam, Linked list) je kontejner určený k ukládání dat předem neznámé délky. Základní stavební jednotkou spojového seznamu je uzel, který vždy obsahuje ukládanou hodnotu a ukazatel na následující prvek. Varianty spojového seznamu Jednosměrně zřetězený seznam Jednosměrně zřetězený seznam je základní variantou této datové struktury, ve které jednotlivé uzly obsahují kromě dat pouze ukazatel na další uzel (poslední uzel ...

Binární pravidelný orientovaný strom Z hlediska teorie grafů je stromem každý souvislý graf bez kružnic o hranách. Jedná se o hierarchickou strukturu, kde každý má otec 0 až mnoho dětí a každé dítě právě jednoho otce takovým způsobem, že v této struktuře nejsou cykly. Uzel, který je praotcem všech ostatních uzlů nazveme kořenem (z pohledu teorie grafů tím vytvoříme orientovaný strom). Uzel, který nemá žá...

Zásobník Zásobník (stack) je jednou ze základních datových struktur, která se využívá především pro dočasné ukládání dat v průběhu výpočtu. Zásobník data ukládá způsobem, kterému se říká LIFO - last in, first out - čili poslední vložený prvek jde na výstup jako první, předposlední jako druhý a tak dále. Opačným způsobem funguje datový typ fronta - FIFO - first in, first out. Základní operace Abstr...