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

Rozšírenie binárnej haldy a algoritmus Heapify

V tomto článku rozšírime pôvodný koncept dátovej štruktúry binárna hromada pre prípad, keď dostaneme už naplnené pole hodnôt, ktoré nám reprezentuje kompletný binárny strom, z ktorého máme vytvoriť binárnu hromadu.

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.

Odkazy

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