BPC-ALD - Skripta_rev2019_2

Následně budeme odspodu procházet nelistové uzly a budeme ověřovat, zda splňují podmínku 
haldy vzhledem ke svým následníkům. Tedy budeme postupně brát následující uzly  

0

1

2

2

1

2

,

...,

,

,

u

u

u

u

n

n

−

−

v tomto  pořadí  a  u  každého  z  těchto  uzlů  ověříme,  zda  prvek  v něm  uložený  není  menší  než 
prvek v některém z jeho následníků. Pokud ano, uděláme výměnu dle následujícího schématu: 

Jestliže  došlo  k  výměně,  je  nyní  v příslušném  následníku  jiný  prvek,  čímž  může  u  něho  dojít 
k narušení  podmínky  haldy  vzhledem  k prvkům  v jeho  následnících.  Musíme  tedy  obdobné 
srovnání (a případnou výměnu) nyní provést pro tohoto následníka. Takto budeme postupovat 
směrem dolů tak dlouho, dokud nedojdeme buďto k uzlu, u kterého výměna není nutná, anebo k 
uzlu, který už žádné následníky nemá (listu). 

Fáze 2 – vlastní třídění 

Třídění probíhá 
přesunem  
prvků z kořenu 
do listového 
uzlu haldy. 

u

7

u

8

u

9

u

10 u11

u

12 u13

u

14

- 2

, kde h je následně zaokrouhleno dolů na nejbližší celé číslo (operace floor).

:

− 43 − 

Z vlastností  haldy  plyne,  že  v jejím  kořenu  je  největší  prvek.  Ten  vyměníme  s prvkem 
v posledním  listu  haldy.  O  tento  list  následně  haldu  zkrátíme  a  pro  nový  prvek  v kořenu 
ověříme, zda splňuje vlastnost haldy vzhledem ke svým následníkům. Pokud ne, vyměňujeme 
prvky mezi uzly a jejich následníky tak dlouho, až všechny splňují vlastnost haldy. Jde o stejný 
postup,  jakým  jsme  ve  fázi  vytváření haldy  prováděli  výměny  prvků  mezi  nelistovými  uzly  a 
jejich následníky.