Triedenie výberom: Rozdiel medzi revíziami
Skočit na navigaci
Skočit na vyhledávání
| Riadok 4: | Riadok 4: | ||
__TOC__ | __TOC__ | ||
| − | ==Heapify== | + | ==Rozšírenie binárnej haldy a algoritmus Heapify== |
| − | V tomto článku rozšírime pôvodný koncept dátovej štruktúry [[Hromada|binárna hromada]] | + | V tomto článku rozšírime pôvodný koncept dátovej štruktúry [[Hromada|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í: | |
# 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 17: | Riadok 17: | ||
\end{align} | \end{align} | ||
</math> | </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. | ||
==Heap Sort== | ==Heap Sort== | ||
==Selection Sort== | ==Selection Sort== | ||
Verzia zo dňa a času 17:30, 1. apríl 2021
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í:
- 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]
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.
