BPC-ALD - Skripta_rev2019_2

Potřebný čas: 2 hodiny 

Poslední  popisovaná  metoda  vnitřního  třídění  používá  k třídění  haldu.  Halda  je  určitý  typ 
binárního stromu. V každém jeho uzlu je jeden tříděný prvek. Dále mezi prvkem v uzlu a prvky 
uloženými  v jeho  následnících  (má-li  nějaké)  platí  vztah,  že  prvek  v  uzlu  má  z nich  největší 
hodnotu. 

Popis algoritmu 

Proces třídění má dvě fáze – vytvoření haldy a vlastní třídění. 

Fáze 1 – vytvoření haldy 

V první fázi vytvoříme haldu. Halda je binární strom a jak již bylo uvedeno v kapitole popisující 
stromovou  strukturu,  optimální  je  vyvážený  binární  strom.  V něm  jsou  všechny  vrstvy  zcela 
zaplněné  až  na  poslední  vrstvu,  která  jediná  může  být  neúplná.  Připomeňme,  že  vrstvou  jsme 
nazvali  množinu  uzlů,  které  mají  od  kořene  stejnou vzdálenost,  tedy  leží  na  stejné  vodorovné 
úrovni. Vzhledem k tomu, že pro implementaci haldy, jak si ukážeme na konci, používáme pole 
a pole je běžně indexováno od 0, budeme i uzly haldy indexovat od 0. 

Halda je 
specifický binární 
strom.

Haldu 
sestavujeme jako 
vyvážený strom.

E

Symbolická značka pro haldu

− 42 − 

Všimněme si specifické vlastnosti indexů jednotlivých uzlů ve vyváženém binárním stromu: 

•  Uzly ve vrstvě k mají indexy v rozmezí

)

1

(

2

...

1

2

+

−

k

k

•  Následníci (existují-li) uzlu s indexem i mají indexy 2∗i+1 a 2∗i+2, tj. následníci uzlu ui 

jsou uzly u2∗i+1 a u2∗i+2 

Nejdříve si z počtu tříděných prvků n vypočítáme výšku haldy, označme ji h: 

)

(

log

2 n

h

=

Sestavíme si vyvážený binární strom této výšky s n uzly a zaplníme ho tříděnými prvky, tj. do 
každého uzlu dáme jeden tříděný prvek.