Triedenie výberom: Rozdiel medzi revíziami
Skočit na navigaci
Skočit na vyhledávání
| Riadok 4: | Riadok 4: | ||
__TOC__ | __TOC__ | ||
| − | == | + | ==Heapify== |
| + | V tomto článku rozšírime pôvodný koncept dátovej štruktúry [[Hromada|binárna hromada]] Keďže hromada je špeciálny typ kompletného binárneho stromu, môžeme využiť nasledovné zákonitosti: | ||
| − | Každý kompletný binárny strom môže byť reprezentovaný ako dátová štruktúra pole, pričom | + | Každý kompletný binárny strom môže byť reprezentovaný ako dátová štruktúra pole, pričom platí: |
# Koreň stromu je vždy prvý prvok v poli (v našom prípade prvok na 0-tej pozícii). | # 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: | # Pre ľubovoľný index <math>i</math> z intervalu <math> \langle 0 \ ; \ \text{dĺžka} - 1 \rangle </math> platia nasledovné rovnice: | ||
| Riadok 13: | Riadok 14: | ||
\text{ľavý potomok} &= 2i + 1 && (1) \\ | \text{ľavý potomok} &= 2i + 1 && (1) \\ | ||
\text{pravý potomok} &= 2i + 2 && (2) \\ | \text{pravý potomok} &= 2i + 2 && (2) \\ | ||
| − | \text{rodič} &= \left \lfloor \frac{i - 1}{2} \right \rfloor && (3) | + | \text{rodič} &= \left \lfloor \frac{i - 1}{2} \right \rfloor \quad (\text {okrem} \ i = 0) && (3) |
\end{align} | \end{align} | ||
</math> | </math> | ||
| − | |||
==Heap Sort== | ==Heap Sort== | ||
==Selection Sort== | ==Selection Sort== | ||
Verzia zo dňa a času 17:13, 1. apríl 2021
Heapify
V tomto článku rozšírime pôvodný koncept dátovej štruktúry binárna hromada Keďže hromada je špeciálny typ kompletného binárneho stromu, môžeme využiť nasledovné zákonitosti:
Každý kompletný binárny strom môže byť reprezentovaný ako dátová štruktúra pole, pričom platí:
- 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 \quad (\text {okrem} \ i = 0) && (3) \end{align} [/math]
