04.1 Binární minimová halda
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
# Binární minimová halda
- Heap
- Uchovává navzájem porovnatelné prvky - označujeme je klíče
- Má tvar binárního stromu
- Ve vrcholech uložena data (klíče)
- Tvar:
- Všechny hladiny kromě poslední musí mít plně obsazené
- Poslední hladina musí být zaplněna od levého okraje k pravému (nemusí být plně zaplněná)
- Haldové uspořádání: ^haldove-usporadani
- Když pro každou dvojici otce a syna podívám na klíče, klíč otce musí být $\le$ klíče syna
- Globální minimum je nutně v kořeni
# Počet hladin
- Binární halda s $n$ prvky má $\floor*{\log{n}} + 1$ hladin
Důkaz
- Binární strom s $h \ge 1$ úplnými hladinami má $n = 2^{0}+2^{1}+2^{2}+\cdots + 2^{h-1} = 2^{h}-1$ vrcholů
- Vzhledem ke tvaru hladiny přibude nová hladina jen, když počet prvků $n$ vzroste z $2^{h}-1$ na $2^h$
- Funkce $\floor{\log{n}}$ se právě při této změně $n$ zvětší o 1, tedy pro $n = 2^{h}-1$ je počet hladin $h = (h-1)+1 = \floor{\log{(2^{h}-1})}+1$
# Počet listů
- Binární halda s $n \ge 3$ má $\floor*{n/2}$ vnitřních vrcholů a $\ceil*{n/2}$ listů