The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

--- statnice:bakalar:b0b36prp [2025/05/11 10:19] – [Řídící struktury] mistrjirka
+++ statnice:bakalar:b0b36prp [2025/05/11 15:17] (current) – external edit 127.0.0.1
@@ Line 14: / Line 14: @@
   * **Datové struktury reprezentovatelné polem** – kruhový buffer, prioritní fronta a halda.
   * **Využití prioritní fronty** – v hledání nejkratší cesty v grafu.
 ===== 1. Řídící struktury =====
-==== Podmínky ====
+<markdown>
-<code>
-if(condition){ //condition should be boolean, but can also be any type of integer where 0 = false, else = true
+## Řídicí struktura
+Řídicí struktury umožňují řídit tok vykonávání příkazů v programu.
+- **Sekvenční struktura** – příkazy se vykonávají v pořadí, jak jsou zapsány.
+- **Větvení** – `if`, `if...else`, `switch`.
+- **Cykly** – `for` (pokud známe počet opakování), `while`, `do...while` (provádí tělo alespoň jednou).
+Příklad větvení:
+```c
+if(condition){ //condition is integer where 0 = false, anything else = true
  // code condition is true
 }else{
  // code condition is false
 }
-</code>
+```
-==== Cykly ====
+## Cykly
+```c
+// může vypadat for(int i = 0; i < 5; i++) nebo také můžeme udělat for(;some_condition;), oboje je valid
+for(initialization; condition; increment/decrement)
+{
+ // code
+ break; // lze použít na dostání se z cyklu
+ continue; // skočí do na začátek cyklu
+}
+while(condition)
+{
+ // code
+ break; // lze použít na dostání se z cyklu
+ continue; // skočí do na začátek cyklu
+};
+```
+## Výrazy
+Výraz je kombinace operandů (proměnná, konstanta, volání funkce) a operátorů. Výraz má hodnotu a typ.
+Pozor: v C není definováno pořadí vyhodnocení podvýrazů! (např. `a = a++ + ++a;` → nedefinované chování)
+## Funkce
+Blok kódu, který má název, parametry a návratovou hodnotu.
+V C každá funkce musí být definována nebo deklarována (prototyp).
+Program začíná ve funkci `int main(int argc, char* * argv`.
+Vlastnosti:
+- Parametry se předávají **hodnotou** (call by value), pro předání odkazem se používají ukazatele.
+- C dovoluje **rekurzi** (funkce může volat sama sebe).
+- Funkce nemohou být vnořené.
+- Funkce s návratovým typem `void` je procedura.
+Příklad funkce:
+```c
+return_type function_name(parameters)
+{
+  // code
+  // for non void functions, we can use `return` to return a value of the return type
+}
+```
+Příklad běžné funkce:
+```c
+int max(int a, int b) {
+    return (a > b) ? a : b;
+}
+```
+## Nedefinované chování
+Nedefinované chování je vlastnost jazyka C, ve výsledky znamená, že výstup chování kódu není definované a může se lišit v závislosti na kompilátoru, operačním systému nebo architektuře. Jedná se například o: dělení nulou, přetečení signed integeru, dereference null pointeru, přístup k paměti mimo alokovanou paměť, použití proměnné bez inicializace, atd.
+Může se lišit mezi překladači nebo mezi běhy programu.
+Příklady:
+- Přetečení `signed int`
+- Dělení nulou
+- Dereference neplatného ukazatele (`NULL`)
+- Přístup k neinicializované proměnné
+- Vícenásobné změny hodnoty proměnné v jediném výrazu (např. `a = a++ + ++a`)
+Jazyk C umí využít nedefinované chování k optimalizaci kódu, protože kompilátor může předpokládat, že se takové chování v programu nikdy nevyskytne.
+Například pokud přičteme k signed integeru 1 a poté v podmínce zkontrolujeme, zda se proměnná zmenšila, kompilátor může předpokládat, že se nikdy nezmenší, protože by to znamenalo přetečení signed integeru a to je nedefinované chování. Proto může kompilátor optimalizovat kód tak, že podmínku vynechá a kód zrychlí (samozřejmě toto může být velmi problémové, pokud se v programu přetečení signed integeru vyskytuje).
+Například u přetečení `signed int` může kompilátor předpokládat, že k tomu nikdy nedojde a podle toho optimalizovat kód.
+## Coding style a čitelnost
+Kódovací styl je způsob, jakým je kód napsán. Existuje mnoho různých stylů, ale většina z nich se snaží o to, aby byl kód čitelný a srozumitelný.
+Například:
+- Používat mezery mezi operátory a operandami
+- Používat odsazení pro bloky kódu
+- Používat popisné názvy proměnných a funkcí
+- Používat komentáře k vysvětlení složitějších částí kódu
+- Používat jednotný styl pro pojmenovávání proměnných a funkcí (např. camelCase, snake_case)
+- Používat krátké funkce, které dělají jednu věc
+- Používat konstanty místo magických čísel
+- Používat funkce pro opakující se kód
+- Udržovat nejmenší scope proměnných.
+Srozumitelnost kódu je důležitá, protože pomáhá ostatním (a i nám) pochopit, co kód dělá. Čitelný kód je také snazší udržovat a opravovat. Je dobré mít jednotný styl v celém projektu, aby byl kód konzistentní a snadno čitelný.
+# 2. Dekompozice programu
+Dekompozice je proces ve kterém se komplexní kus logiky programu rozdělí na menší části pro lepší čitelnost. Většinou se jedná o rozdělení programu do jednotlivých funkcí, rozdělení do více souborů atd...
+## Dekompozice programu do funkcí
+Dekompozici do funkcí má smysl dělat hlavně ve dvou situacích:
+### 1. Odstranění opakující se logiky
+Když se v programu opakuje stejný (nebo hodně podobný) kód, vyplatí se jej **extrahovat** do samostatné funkce a tu pak volat tam, kde je potřeba. Přináší to několik výhod:
+* **Čitelnost** – program se zkrátí a je hned jasné, *co* se v jednotlivých částech děje.
+* **Údržba** – změny děláš na jednom místě, takže nehrozí, že zapomeneš upravit některou kopii kódu.
+* **Potenciální rychlost** – menší binárka se lépe vejde do instrukční cache CPU, což může přinést drobný výkonový bonus.
+### 2. Zkrácení přerostlých bloků kódu
+Když funkce nabobtná do desítek či stovek řádků, stává se nečitelnou. Řešení:
+. Najdi **logické podbloky** a každý přesuň do nové, srozumitelně pojmenované funkce.
+. Původní (hlavní) funkce pak slouží jen jako „dirigent“, který volá menší, soustředěné části.
+> **Poznámka k výkonu:** Každé volání funkce má overhead. Pokud jde o výkonnostně citlivou část, použít klíčové slovo **`inline`**. Překladač vloží kód funkce přímo na místo volání a skok se tím eliminuje.
+## Dekompozice programu do souborů
+V C se zdroják obvykle dělí na **implementační soubory** (`.c`) a **hlavičkové soubory** (`.h`). Hlavní motivy rozdělení:
+### 1. Logická modularizace
+* **Doménové vrstvy** – např. `math.c`, `io.c`, `net.c`; každá řeší jasně vymezenou oblast.
+* **Zapouzdření** – veřejné rozhraní definuješ v `.h`, detaily necháš „schované“ v `.c`.
+* **Jasné závislosti** – co modul nepotřebuje, to ne‐`#include`-uje.
+### 2. Zrychlení překladů
+* Překladač kompiluje každý `.c` soubor zvlášť do objektu (`.o`).
+* Při drobné změně stačí přeložit jen dotčené moduly a pak je znovu slinkovat, což výrazně šetří čas u větších projektů.
+### 3. Znovupoužití a knihovny
+* Dobře navržený modul zabalíš do statické (`.a`) nebo sdílené (`.so`, `.dll`) knihovny a použiješ jinde.
+* Hlavička (`.h`) pak slouží jako kontrakt pro všechny projekty, které knihovnu linkují.
+## Předávání argumentů funkci
+### Funkce nemá argumenty
+Když chceme vytvořit funkci která nebude mít žádné argumenty je lepší psát:
+```c
+int nazev_funkce(void) {
+  // code
+}
+```
+než:
+```c
+int nazev_funkce() {
+  // code
+}
+```
+To je z toho důvodu že když do listu argumentů přímo napíšeme void tak nás compiler zastaví pokud se funkci pokusíme nějaké argumenty předat. Zatímco v druhém případě funkci můžeme zavolat s argumenty a compiler nás ani nemusí varovat.
+### Funkce s argumenty
+Obecně funkce s argumenty vypadá:
+```c
+return_type function_name(arg1, arg2 .... argn)
+{
+  // code
+}
+```
+Argumenty můžeme předávat dvěma způsoby, buď by-value nebo by-reference. Kde V prvním případě zkopírujeme hodnotu proměnné a předáme funkci kopii, v druhém případě předáme funkci odkaz na paměť proměnné. Předávat odkazy v případě větších datových typů může mít rychlostní výhody, ale musíme počítat s tím že jakékoliv změny v promenně ve funkci se propíšou i mimo tuto funkci, takže funkce může mít neočekávané side effects.
+### Návratová hodnota
+Funkce může vracet hodnotu a také nemusí. V přpadě kdy nevrací hodnotu používáme return type `void nazev_funkce` před jménem funkce, pokud vrací hodnoty použijeme datový typ před názvem proměnné např.: `int nazev_funkce`.
+### Rekurzivní funkce
+Rekurzivní funkce je taková, která **volá sama sebe**, dokud se nedostane k **základnímu případu** (*base case*).
+V matematice se rekurzivní definice vyskytují často, takže pro některé algoritmy bývá rekurzivní zápis přirozenější a srozumitelnější než iterativní varianta. Každé volání funkce ale znamená jistý overhead (uložení návratové adresy a lokálních proměnných na zásobník), takže **hluboká rekurze** může být pomalejší a náročnější na paměť.
+#### Ukázka — faktoriál `n!`
+```c
+/* Rekurzivní výpočet n!
+   base case:      0! = 1
+   recursive step: n! = n x (n-1)!
+*/
+unsigned long long factorial(unsigned int n)
+{
+    if (n == 0)            // základní případ
+        return 1;
+    return n * factorial(n - 1); // rekurzivní volání
+}
+```
+# 3.  Datové typy
+Datové typy v C jsou:
+- _Bool (v c spíše pseudotyp)
+- char
+- int
+- short
+- long
+- long long
+- float
+- double
+(mají definovanou velikost ve standardu C, kdy short $\leq$ int $\leq$ long, ale závisí na compileru)
+Proměnná pak musí mít zadefinovaný typ:
+```c
+int a = 5;
+char b = 'a';
+```
+proměnné dále můžou mít modifikátory jako:
+- `signed` - má jak kladné tak záporné hodnoty
+- `unsigned` - má pouze kladné hodnoty
+- `static` - hodnota se uchovává mezi voláním funkce, je uložena ve static data
+- `const` - hodnota se nemění
+- `volatile` - hodnota se může měnit mimo program (např. hardware)
+- `extern` - proměnná je definována v jiném souboru
+V C není datový typ string. Textové řetězce se reprezentují jako pole znaků zakončené `\0`.
+```c
+char text[] = "Ahoj";
+char *text2 = "Ahoj"; // konstanta
+```
+pozor na rozdíl mezi `const int *` - konstantní hodnota, `const int * const` - konstantní pointer na konstantní hodnotu, a `int * const` - konstantní pointer na proměnnou, v C lze ale vše přetypovat, takže to není nutně konstantní
+- konstantní pointer nelze přesměrovat na jinou proměnnou, ale hodnota na kterou ukazuje se může měnit
+- konstantní hodnota se nemění, ale pointer se může přesměrovat na jinou proměnnou
+- konstantní pointer na konstantní hodnotu se nemění, ani hodnota na kterou ukazuje
+můžeme includovat knihovnu `inttypes.h` která nám umožní používat typy se specifickou velikostí, jako například `uint8_t`, pro 8 bit unsigned integer.
+v knihovně `limits.h` se dozvíme velikosti, například `INT_MIN` a `INT_MAX`, které nám říkají jakých hodnot může nabývat proměnná typu int.
+Změna datového typu je možná pomocí `cast`:
+```c
+int a = 5;
+float b = (float)a; // a je převedeno na float
+```
+Pointer je proměnná která obsahuje adresu jiné proměnné.
+```c
+int a = 5;
+int *p = &a; // p je pointer na a
+int b = *p; // b je hodnota na kterou p ukazuje
+*p = 10; // změní hodnotu a na 10
+```
+datový typ `void*` je speciální typ, který může ukazovat na jakýkoli typ dat.
+# 4. Pole, ukazatel, textový řetězec
+Pole v C můžeme definovat dvěma způsoby, statické pole:
+```c
+int x[5]; // pole of velikosti 5
+x[0] = 1; // první prvek pole
+x[1] = 2; // druhý prvek pole
+x[2] = 3; // třetí prvek pole
+//nebe pomocí pointer aritmetiky:
+*(x + 3) = 1 // čtvrtý prvek pole
+```
+takto vytvořené pole má statickou velikost a je uloženo na stacku.
+a nebo dynamické pole:
+```c
+int *x = malloc(2 * sizeof(int)); // pole of velikosti 5
+x[0] = 1; // první prvek pole
+x[1] = 2; // druhý prvek pole
+free(x); // uvolnění paměti
+```
+takto vytvořené pole je umístěno na haldě, pro získání místa na haldě musíme o místo zažádat pomocí `malloc` a pak je správné ho na konci uvolnit pomocí `free`.
+void* je speciální ukazatel, který může ukazovat na libovolný typ dat a je běžně používán pro obecné funkce pracující s různými datovými typy.
+# 5. Zpracování vstupů a ošetření chybových stavů
+Můžeme použít funkce `scanf`, `fscanf` a podobné.
+Měli bychom sledovat návratovou hodnotu těchto funkcí, abychom věděli jestli nenastala chyba při čtení:
+```c
+#define ERROR_INPUT -1
+int ret = 0;
+ret = scanf("%d", &input);
+if (ret == EOF){
+  return ERROR_INPUT;
+}
+```
+Pro načítání stringů lze použít funkci `fgets` pro načtení řetězce o zadané velikosti, abychom předešli přetečení bufferu.
+```c
+#define BUF_SIZE 256
+char buf[BUF_SIZE];
+fgets(buf, sizeof(buf), stdin);
+```
+# 6. Zápis, překlad a spouštění programu v C
+Soubory píšeme do souborů s příponom `.c` a knihovny do `.h`, includování probíhá pomocí makra `#include`.
+Překlad probíhá následujícími kroky:
+- *Preprocesor*: příkazy preprocesoru se zpracují (`#include`, `#define`, #ifndef` apod.), odstraní se komentáře, výsledek se uloží
+o `.i` souborů
+- *Kompilátor*: `.i` soubory se přeloží z C kódu do assembleru a výsledek se uloží do `.s` souboru.- *Asembler*: přeloží `.s` soubory do objektových souborů `.o`, zatím bez absolutních adres
+- *Linker*: objektové soubory se slinkují (přeloží se adresy pro volání funkcí, nastavuje enviroment pro předávání argumentů, atd...) do spustitelného souboru
+Soubor lze zkompilovat se statickými (`#include "library.h"`) nebo sdílenými (`#include <library.h>`) knihovnami (staticky například prolepší přenositelnost, ale zvětšuje velikost binárního souboru)
+Spuštění souboru nezačíná ve funkci `main` ale ve funkci `_start`, která připraví prostředí pro spuštění programu a zavolá funkci main. Funkce main pak vrací hodnotu, která se předává operačnímu systému
+jako návratová hodnota programu. (tu můžeme vypsat pomocí `echo $?` v shellu).
+# 7. Abstraktní datové typy (ADT)
+Abstraktní datové typy (ADT) představují konceptuální model datových struktur, kde je definováno chování (operace) bez ohledu na konkrétní implementaci. V jistých aspektech připomínají zapouzdření tříd v objektově orientovaných jazycích.
+## Příklad
+Uděláme si ADT Stacku. Nejdříve si vytvoříme hlavičkový soubor kde definujeme interface.
+```c
+typedef struct Stack Stack;      // neúplný typ
+Stack *stack_create(void);
+bool    stack_push(Stack *, int);
+bool    stack_pop (Stack *, int *out);
+void    stack_destroy(Stack *);
+```
+Tento interface je většinou vše co uživatel vidí, definuje jak vytvoříme datový typ a operace které s ním můžeme dělat. Nemusíme se starat jak funguje push nebo pop a co přesně dělá. Stačí když víme co jednotlivé funkce dělají.
+K tomuto interfacu existuje poté specifická implementace. Která může vypadat takhle:
+```c
+struct Stack { size_t top, cap; int *buf; };
+Stack *stack_create(void) {
+    Stack *s = calloc(1, sizeof *s);
+    if (!s) return NULL;
+    s->cap = 4;
+    s->buf = malloc(s->cap * sizeof *s->buf);
+    return s && s->buf ? s : (free(s), NULL);
+}
+static bool grow(Stack *s) {
+    size_t n = s->cap * 2;
+    int *tmp = realloc(s->buf, n * sizeof *tmp);
+    if (!tmp) return false;
+    s->buf = tmp;
+    s->cap = n;
+    return true;
+}
+bool stack_push(Stack *s, int v) {
+    if (s->top == s->cap && !grow(s)) return false;
+    s->buf[s->top++] = v;
+    return true;
+}
+bool stack_pop(Stack *s, int *out) {
+    if (!s->top) return false;
+    if (out) *out = s->buf[--s->top];
+    return true;
+}
+void stack_destroy(Stack *s) {
+    if (s) { free(s->buf); free(s); }
+}
+```
+# 8. Jednosměrný a obousměrný spojový seznam
+## Spojové seznamy
+Dynamická struktura, kde každý prvek obsahuje hodnotu a odkaz na další prvek.
+- **Jednosměrný** – každý prvek ukazuje na následující.
+- **Obousměrný** – prvky obsahují odkazy na předchozí i následující prvek.
+- **Kruhový** – poslední prvek ukazuje zpět na první.
+Výhoda: **flexibilní velikost**. Nevýhoda: **vyšší paměťová režie**
+Může být jednoduše naimplementován pomocí dvou struktur, node:
+```c
+typedef struct node {
+  void* data;
+  struct node *next;
+} node_t;
+```
+a linked list:
+```c
+typedef struct linked_list {
+  node_t *head;
+} linked_list_t;
+```
+Pro oboustraný linked list, pouze přidáme zpětný pointer do struktry node:
+```c
+typedef struct node {
+  void* data;
+  struct node *next;
+  struct node *prev;
+} node_t;
+```
+a poslední prvek do linked listu:
+```c
+typedef struct linked_list {
+  node_t *head;
+  node_t *tail;
+} linked_list_t;
+```
+v normálním spojovém seznamu má poslední prvek hodnotu next NULL, v obousměrném má head->prev NULL a tail->next NULL.
+# 9. Nelineární spojové struktury
+## Stromy – základní pojmy
+- **Cesta** – posloupnost uzlů od kořene k uzlu.
+- **Délka cesty** – počet hran mezi kořenem a uzlem.
+- **Hloubka uzlu** – délka cesty od kořene.
+- **Výška stromu** – maximální hloubka uzlu ve stromu.
+- **Šířka stromu** – počet uzlů na stejné úrovni.
+- **Vyvážený strom** – uzly rovnoměrně rozložené, nejmenší možná výška.
+Příklad uzlu v C:
+```c
+typedef struct Node {
+    int data;
+    struct Node* left;
+    struct Node* right;
+} Node;
+```
+Například strom:
+```c
+typedef struct node {
+  void* data;
+  struct node *children;
+} node_t;
+```
+```c
+typedef struct tree {
+  node_t *root;
+} tree_t;
+```
+## Typy stromů
+### Uspořádaný strom
+- Potomci každého uzlu jsou uspořádáni (například podle klíče).
+### Neuspořádaný strom
+- Čistě strukturální strom, pořadí potomků není určeno.
+## Binární vyhledávací strom (BST)
+- Každý uzel má maximálně 2 potomky (levý a pravý podstrom).
+- Levý potomek obsahuje menší hodnotu, pravý potomek větší hodnotu než rodič.
+- Slouží k rychlému vyhledávání, vkládání a mazání dat (průměrně O(log n), v nejhorším O(n) u nevyváženého stromu).
+- Implementace je většinou rekurzivní.
+- Základní typy:
+  - **Plný binární strom** – všechny listy na stejné hloubce.
+  - **Úplný binární strom** – každý vnitřní uzel má dva potomky.
+  - **Vyvážený binární strom** – hloubka listů se liší maximálně o 1.
+### Matematické vlastnosti
+- Počet uzlů: `n`
+- Hloubka stromu: `h`
+- Minimální počet uzlů: `n = 2h + 1`
+- Maximální počet uzlů: `n = 2(h+1) - 1`
+- Počet listů: `ceil(n/2)`
+## Implementace binárního stromu v C
+```c
+typedef struct node {
+    int value;
+    struct node *left;
+    struct node *right;
+} node_t;
+node_t *tree = NULL;
+```
+## Procházení stromu
+### BFS (do šířky)
+- Prochází se úrovně stromu po vrstvách.
+### DFS (do hloubky)
+- Existují 3 základní metody:
+  - **Preorder**
+    ```c
+    void preorder(node_t *root) {
+        if (root) {
+            printf("%d ", root->value); // akce
+            preorder(root->left);
+            preorder(root->right);
+        }
+    }
+    ```
+  - **Inorder**
+    ```c
+    void inorder(node_t *root) {
+        if (root) {
+            inorder(root->left);
+            printf("%d ", root->value); // akce
+            inorder(root->right);
+        }
+    }
+    ```
+  - **Postorder**
+    ```c
+    void postorder(node_t *root) {
+        if (root) {
+            postorder(root->left);
+            postorder(root->right);
+            printf("%d ", root->value); // akce
+        }
+    }
+    ```
+## Vyhledávání v binárním vyhledávacím stromu (BST)
+```c
+node_t* search(node_t* root, int key) {
+    if (!root || root->value == key)
+        return root;
+    if (key < root->value)
+        return search(root->left, key);
+    else
+        return search(root->right, key);
+}
+```
+# 10. Datové struktury reprezentovatelné polem
+## Zásobník (Stack)
+Zásobník je lineární datová struktura pracující na principu **LIFO (Last In, First Out)** – poslední prvek vložený do zásobníku je první, který se odebere.
+### Základní operace:
+- **push**: vloží prvek na vrchol zásobníku.
+- **pop**: odebere a vrátí prvek z vrcholu zásobníku.
+- **peek** (top): vrátí hodnotu vrcholu zásobníku, aniž by ji odebral.
+- **isEmpty**: zjistí, zda je zásobník prázdný.
+Zásobník lze implementovat pomocí pole nebo spojového seznamu. Používá se například při rekurzi, parsování výrazů nebo při realizaci funkcí volání v programech.
+## Fronta (Queue)
+Fronta je lineární datová struktura pracující na principu **FIFO (First In, First Out)** – první prvek vložený do fronty je první, který se odebere.
+### Základní operace:
+- **enqueue**: vloží prvek na konec fronty.
+- **dequeue**: odebere a vrátí prvek z čela fronty.
+- **peek** (front): vrátí hodnotu na čele fronty, aniž by ji odebral.
+- **isEmpty**: zjistí, zda je fronta prázdná.
+Fronta se používá například při plánování procesů, správě úloh, nebo v simulacích, kde je potřeba zachovat pořadí požadavků.
+## Prioritní fronta – spojový seznam nebo pole
+- Každý prvek má přiřazenou prioritu. Při vybírání se vždy vybere prvek s nejvyšší nebo nejnižší prioritou (dle implementace).
+- Prioritní frontu lze implementovat jako:
+  - **spojový seznam** (pomalé vybírání O(n), rychlé vkládání O(1)),
+  - **pole** (pomalé vybírání O(n)),
+  - **haldu (heap)** (rychlé vybírání i vkládání O(log n)).
+Příklad struktury polem:
+```c
+typedef struct {
+    void **queue;
+    int *priorities;
+    int count;
+    int head;
+    int tail;
+} queue_t;
+```
+## Halda (heap)
+- Binární plný strom s vlastností haldy:
+  - Rodič ≤ potomci (min-heap) nebo rodič ≥ potomci (max-heap).
+- Prvky jsou uloženy v poli.
+### Indexování:
+- levý potomek: $2\cdot i + 1$
+- pravý potomek: $2\cdot i + 2$
+- rodič: $(i - 1) / 2$
+### Základní operace haldy
+#### Insert / Push
+- Přidá prvek na konec pole (na první volné místo).
+- Prvek se **"bublá nahoru"** (heapify-up), dokud není splněna vlastnost haldy (porovnává se s rodičem).
+- Složitost: **O(log n)**.
+#### Pop
+- Odebere prvek z kořene (index 0 = minimum/min-heap).
+- Poslední prvek se přesune na kořen a **"bublá dolů"** (heapify-down), dokud není splněna vlastnost haldy.
+- Složitost: **O(log n)**.
+#### Peek
+- Vrátí hodnotu na kořeni (nejmenší / největší prvek podle typu haldy), aniž by prvek odstranila.
+- Složitost: **O(1)**.
+### Výhody haldy
+- V porovnání s prostou prioritní frontou v poli má halda efektivní složitost operací.
+- Halda je ideální pro implementaci **prioritní fronty**, například pro algoritmy hledání nejkratší cesty (Dijkstra, A*).
+# 11. Využití prioritní fronty – hledání nejkratší cesty v grafu
+## Dijkstrův algoritmus
+. Nastavíme vzdálenosti všech uzlů na nekonečno (`INT_MAX`), startovací uzel na 0.
+. Vložíme startovací uzel do prioritní fronty (haldy).
+. Dokud fronta není prázdná:
+   - Vybereme uzel s nejmenší vzdáleností.
+   - Aktualizujeme vzdálenosti sousedů.
+   - Přidáme sousedy do fronty, pokud se vzdálenost zmenšila.
+Příklad:
+```c
+typedef struct {
+    int vertex;
+    int distance;
+} PriorityQueueNode;
+```
+Složitost: $O((V + E) \cdot log V)$
+Dijkstra algoritmus předpokládá, že všechny hrany mají nezáporné váhy. Pro grafy s negativními hranami je vhodnější algoritmus Bellman-Ford.
+## A* algoritmus
+- Modifikace Dijkstra s heuristikou (odhadem vzdálenosti do cíle).
+- Heuristika snižuje počet prozkoumaných uzlů → rychlejší hledání.
+- Nejčastější použití v herní AI, robotice, mapových aplikacích.
+</markdown>

Trace: • syntax

Differences

Search

Navigation

Print/export

Tools

QR Code