4.1 Halda jako struktura

Zakořeněný strom, Binární strom a halda

Definice 4.1 (Zakořeněný strom)

Zakořeněný strom

Zakořeněněný strom je strom \(T\), ve kterém je jeden vrchol \(r \in V(T)\) označen jako kořen
Leží-li \(u\) na (jediné) cestě z \(v\) do kořene, pak \(u\) je předek \(v\) a \(v\) je potomek \(u\). Pokud je navíc \(\{u,v\} \in E(T)\) hrana, říkáme, že \(u\) je otec \(v\) a \(v\) je syn \(u\).
Vrcholy rozdělíme podle vzdálenosti od kořene do hladin: v nulté leží kořen, v první jeho synové, atd.
Hloubka zakořeněného stromu \(T\) je počet jeho hladin.

Pozorování

Všechny \(v \in V(T) − \{r\}\) jsou potomci kořene \(r\) a kořen \(r\) je předkem všech ostatních vrcholů.

Definice 4.2 (Binární strom)

Binární strom

Strom nazveme binární, pokud

je zakořeněný
každý vrchol má nejvýše dva syny
u synů rozlišujeme, který je levý a který pravý.

Definice 4.3 (Binární minimová halda)

Binární minimová halda

Binární minimová halda je datová struktura tvaru binárního stromu, v jehož každém vrcholu \(x\) je uložen jeden klíč \(k(x)\) a která splňuje tyto dvě vlastnosti:

Tvar Haldy: Strom má všechny hladiny kromě poslední plně obsazené. Poslední hladina je zaplněna od levého okraje směrem k pravému.
Haldové uspořádání: Je-li \(v\) vrchol a \(s\) jeho syn, platí

\(k(v) \le k(s)\)

graph TD
    A(["3"]):::level0
    A --> B(["5"]):::level1
    A --> C(["7"]):::level1
    B --> D(["11"]):::level2
    B --> E(["6"]):::level2
    C --> F(["9"]):::level2

    classDef level0 fill:#00af00,stroke:#000,stroke-width:2px,color:#fff,shape:circle,align:center;
    classDef level1 fill:#0000af,stroke:#000,stroke-width:2px,color:#fff,shape:circle,align:center;
    classDef level2 fill:#afaf00,stroke:#000,stroke-width:2px,color:#fff,shape:circle,align:center;

Pozorování

Na cestě vedoucí z libovolného vrcholu do kořene tvoří klíče nerostoucí posloupnost.
V kořeni je tedy globální minimum ze všech klíčů.