Triedenie výberom: Rozdiel medzi revíziami
Skočit na navigaci
Skočit na vyhledávání
| Riadok 5: | Riadok 5: | ||
==Algoritmus Heapify== | ==Algoritmus Heapify== | ||
| + | |||
| + | Každý kompletný binárny strom môže byť reprezentovaný ako dátová štruktúra pole, pričom platia tieto zákonitosti: | ||
| + | # Koreň stromu je vždy prvý prvok v poli (v našom prípade prvok na 0-tej pozícii). | ||
| + | # 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 && (3) | ||
| + | \end{align} | ||
| + | </math> | ||
| + | |||
==Heap Sort== | ==Heap Sort== | ||
==Selection Sort== | ==Selection Sort== | ||
Verzia zo dňa a času 16:41, 1. apríl 2021
Algoritmus Heapify
Každý kompletný binárny strom môže byť reprezentovaný ako dátová štruktúra pole, pričom platia tieto zákonitosti:
- Koreň stromu je vždy prvý prvok v poli (v našom prípade prvok na 0-tej pozícii).
- 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 && (3) \end{align} [/math]
