Triedenie výberom

Algoritmy a programovanie

---

Dátový typ

Štruktúry

Rekurzia

Algoritmy vyhľadávania

Algoritmy triedenia

>Triedenie výmenou
>Triedenie vkladaním
>Triedenie zlučovaním
>Triedenie delením
>Triedenie výberom
>Triedenie - ostatné princípy

Lineárny zoznam

Binárny strom

Numerické algoritmy

Grafové algoritmy

Zlučovací algoritmus Heapify

Algoritmus Heapify predstavuje kľúčový podprogram pre triediaci algoritmus Heap sort. pracuje s dátovou štruktúrou binárna hromada

Všeobecne platí, že každý kompletný binárny strom môžeme byť vyjadrený pomocou poľa s využitím nasledovných zákonitostí:

1. Koreň stromu je vždy prvý prvok v poli (v našom prípade prvok na 0-tej pozícii).
2. Pre ľubovoľný index [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]

Na základe týchto zákonitostí môžeme vytvoriť algoritmus Heapify, vďaka ktorému vieme elegantne uskutočniť operácie s hromadou, ako je vytvorenie hromady z poľa, zmazanie jednotlivých prvkov z hromady, čo sú základné časti triediaceho algoritmu Heap Sort.

Algoritmus Heapify

Ak máme i-ty prvok v poli, pričom oba jeho potomkovia tvoria dve samostatné hromady, potom funkcia Heapify zlúči tieto dve hromady do jednej, pričom i-ty prvok bude jej koreňom.

Základné časti algoritmu

1. Určenie maxima z 2 potomkov i-teho prvku a porovnanie s veľkosťou rodiča.
2. Ak je potomok väčší ako rodič, tak výmena potomka a rodiča.
3. Skontrolovanie ovplyvneného potomka (podstromu).

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

Odkazy

https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_heapify_method.htm