04.3 Nalezení a odstranění minima
$$
\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}}
$$
# Nalezení a odstranění minima
# HeapFindMin()
- Triviální
- Vrať klíč kořene $r$ haldy
- Složitost: $O(1)$
# HeapExtractMin()
- Odstranění minima
- Minimum (kořen) prohodím s koncem haldy (vznikne z něj list, z listu kořen)
- Pro nový kořen bublat dolů (prohození se synem s nižším klíčem - tedy aby o hladinu výš stále bylo nižší číslo)
- Složitost: $O(\log{n})$
- Na každé hladině strávíme $O(1)$ operací, procházených hladin je nejvýše logaritmicky mnoho