Triedenie výberom
Verzia z 19:45, 3. apríl 2021, ktorú vytvoril Matúš Nečas (diskusia | príspevky) (→Algoritmus Heapify)
Obsah
Tento článok je v prvotnom štádiu konštrukcie, zatiaľ je to len hromada myšlienok :)
Heap Sort
Algoritmus Heap Sort pri triedení využíva dátovú štruktúru binárna hromada, ktorú si vytvorí zo vstupného poľa, ktoré máme utriediť a následne zmazaním všetkých jej prvkov dosiahneme utriedené pole.
Hromada, ktorú vytvoríme musí spĺňať nasledovné podmienky:
- 1. Vrchol hromady je vždy prvý prvok v poli (v našom prípade prvok na 0-tej pozícii).
- 2. Pre ľubovoľný prvok uložený na indexe [math]i[/math] z intervalu [math] \langle 0 \ ; \ \text{dĺžka} - 1 \rangle [/math] platia nasledovné rovnice:
- [math] \begin{align} \text{ľavý potomok} &= 2i + 1 && (1) \\ \text{pravý potomok} &= 2i + 2 && (2) \\ \text{rodič} &= \left \lfloor \frac{i - 1}{2} \right \rfloor \quad (\text {okrem} \ i = 0) && (3) \end{align} [/math]
- 3. Každý prvok (uzol) v hromade musí mať väčšiu, alebo rovnakú hodnotu ako jeho potomkovia (MAX HEAP - ak triedime pole od vzostupne).
Algoritmus Heapify
Heapify je kľúčovým podprogramom triediaceho algoritmu Heap Sort.
Základné časti algoritmu
- Určenie maxima z 2 potomkov i-teho prvku a porovnanie s veľkosťou rodiča.
- Ak je potomok väčší ako rodič, tak výmena potomka a rodiča.
- Skontrolovanie ovplyvneného potomka (podstromu).
Slovný opis algoritmu
Ak máme i-ty prvok v poli, pričom oba jeho potomkovia tvoria dve samostatné podhromady, potom funkcia Heapify zlúči tieto dve podhromady do jednej hromady, pričom i-ty prvok bude jej vrcholom.
Vlastnosti algoritmu
- dátová štruktúra: hromada (pole)
- časová zložitosť: lineárna [math]O(n)[/math]
- priestorová zložitosť: konštantná [math]O(1)[/math] pri iteračnej verzii, [math]O(log(N))[/math] pri rekurzívnej verzii
