04 HeapSort
$$
\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}}
$$
# Algoritmus HeapSort
- Halda umožňuje zkonstruovat rychlý alogritmus pro řazení
- Nazývá se HeapSort
- Prvky $x_{1},\dots , x_{n}$ vložíme do pole
- Na toto pole se zavolá HeapBuild
- Poté $n$-krát zavoláme HeapExtractMin a vracené hodnoty vypíšeme do výstupního pole
- Tím vygenerujeme vzestupně seřazenou posloupnost
# Časová složitost
HeapBuild: $O(n)$
HeapExtractMin: $O(n \log{n})$
HeapSort: $O(n)+O(n \log{n}) = O(n \log{n})$