====== Imperativní programování. Programovací jazyk C. Abstraktní datové typy a spojové struktury. ======

[[https://fel.cvut.cz/cz/education/bk/predmety/47/02/p4702606.html|B0B36PRP]] [[https://cw.fel.cvut.cz/wiki/courses/b0b36prp/lectures/start|Webové stránky předmětu]]

  * **Řídící struktury** – výrazy, funkce, nedefinované chování, kódovací (programovací) styly a čitelnost a srozumitelnost programů.
  * **Dekompozice programu** – do funkcí, předávání argumentů funkcím, návratová hodnota, rekurze a volání funkcí.
  * **Datové typy** – vnitřní reprezentace číselných typů, struktury a uniony v C.
  * **Pole, ukazatel, textový řetězec** – dynamická alokace a paměťové třídy.
  * **Zpracování vstupů a ošetření chybových stavů** – práce se soubory.
  * **Zápis, překlad a spouštění programu v C** – vstup, výstup programu a jeho interakce s operačním systémem.
  * **Abstraktní datové typy (ADT)** – definice, příklady specifikací základní ADT.
  * **Jednosměrný a obousměrný spojový seznam** – implementace zásobníku a fronty.
  * **Nelineární spojové struktury** – binární vyhledávací strom, prioritní fronta a halda.
  * **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 =====
<markdown>

## Ří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
}
```

## 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í:

1. Najdi **logické podbloky** a každý přesuň do nové, srozumitelně pojmenované funkce.  
2. 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
1. Nastavíme vzdálenosti všech uzlů na nekonečno (`INT_MAX`), startovací uzel na 0.
2. Vložíme startovací uzel do prioritní fronty (haldy).
3. 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>