BPC-ALD - Skripta_rev2019_2

∗h  operací  (tento  počet  typicky  klesá,  jak  se  halda  postupně  zkracuje).  Opět 

logaritmická složitost pro každý nový prvek v kořenu haldy. Vynásobíme-li ji celkovým počtem 
prvků, dostáváme zase složitost 

Θ(n∗log(n)). 

Závěr: Složitost třídění použitím haldy je 

Θ(n∗log(n)). 

I  když  tato  třídící  metoda  je  založena  na  stromové  struktuře,  při  implementaci  ji  nemusíme 
dynamicky vytvářet pomocí uzlů, ukazatelů atd. Jak už jsem ukázali, následníci uzlu s indexem 
i  mají  indexy  2

∗i+1  (levý  následník)  a  2∗i+2  (pravý  následník).  Strom  se  tímto  dá  snadno 

realizovat pomocí pole, když jeho prvky dáme po řádcích do pole. 

Složitost třídění 
haldou je 
Θ(n

∗log(n)). 

− 47 − 

Kontrolní otázky  

1.  Jakým způsobem sestavíme z posloupnosti prvků haldu? 
2.  Proč haldu sestavujeme jako vyvážený strom? Kdyby nebyl vyvážený, mělo by to nějaký 

vliv na výsledné setřídění prvků? 

3.  Jaká je časová složitost třídění haldou? 

Cvičení   

1.  Tříděním haldou setřiďte podle abecedy následujících sedm písmen. 

2.  Jak bude probíhat třídění haldou pro následující obráceně uspořádanou posloupnost pěti 

písmen: 

Úkoly k textu  

Občas je zapotřebí třídit v opačném pořadí, tj. od největšího prvku k nejmenšímu. Zamyslete se, 
jak by se to realizovalo při třídění haldou.  

Řešení  

1.  Nejprve z prvků sestavíme haldu, postup ukazuje následující obrázek: 

− 48 − 

Následně výměnami prvků mezi kořenem a posledním listem haldy a zkracováním 
haldy provedeme třídění. Následující obrázek ukazuje první čtyři kroky, tj. setřídění 
prvních čtyř písmen: 

2.  Postup sestavení haldy ukazuje následující obrázek: