BPC-ALD - Skripta_rev2019_2

Je zřejmé, že každým krokem se halda zkrátí o jeden uzel. Až nakonec obsahuje jen jeden uzel, 
čímž proces třídění končí. Setříděné posloupnost je na konci v uzlech binárního stromu, který 
jsme  začátku  vytvořili  a  do  kterého  jsme  uložili  tříděné  prvky.  Dostaneme  ji  tak,  že  strom 
procházíme shora po jednotlivých vrstvách směrem dolů, tj. tvoří ji uzly stromu v pořadí 

1

2

1

0

,

...,

,

,

−

−

n

n

u

u

u

u

    . 

Příklad. Nechť tříděné hodnoty jsou 

7  2  8  1  5  3  9  4 

Jejich počet je n=8. Zřejmě log2(8)=3, tedy výška stromu je 3. Strom vytvoříme a do jeho uzlů 

dáme tříděné prvky: 

Vezmeme  poslední  z nelistových  uzlů  u3  a  ověříme  velikost  hodnoty  uložené  v tomto  uzlu 

s hodnotou  v jeho  následníku  u7. Je vidět, že hodnota v následníku je menší a  je tedy potřeba 

výměna hodnot. 

Vezmeme  další  nelistový  uzel  u2.  U  něho  je  nutná  výměna  hodnot  mezi  tímto  uzlem  a  jeho 

pravým následníkem u6. 

Další uvažovaný uzel je u1. Zde je nutná výměna mezi tímto uzlem a jeho pravým následníkem 

u4. 

− 44 − 

Zbývá  poslední  doposud  neuvažovaný  uzel  u0.  U  něho  je  zapotřebí  vyměnit  hodnotu  v něm 

s hodnotou uloženou v jeho pravém následníku u2.  

Je  zřejmé,  že  po  této  výměně  nyní  hodnota  v uzlu  u2  nesplňuje  vlastnost  haldy  a  je  ji  nutno 

vyměnit s hodnotou v pravém následníku u6. 

Nyní můžeme začít třídění. Hodnotu v kořenu vymění s hodnotou v posledním listu u7 a haldu o