11-Trideni_halda_stromy

a

b

c

b

a

c

→

𝑎 < 𝑐
𝑐 > 𝑏

b

c

a

Vytvoření haldy

• Po výměně je v následníkovi s nímž proběhla výměna menší hodnota 

prvku, než v něm byla původně.

• Mohlo tedy dojít k porušení podmínky haldy vzhledem k hodnotám 

prvků v jeho následnících. 

5

2

4

3

2

5

4

3

4

5

2

3

Došlo k porušení 
podmínky haldy

Vytvoření haldy

• Pokud došlo při výměně k porušení podmínky haldy, postupujeme 

směrem dolů a provádíme výměny tak dlouho, dokud nedojdeme k 
uzlu:

• u něhož není výměna nutná
• nebo nemá následníka (je listem).

Vlastní třídění

• Z podmínky haldy plyne, že v jejím kořenovém uzlu je největší prvek.
• Vyměníme hodnotu prvku v kořenovém uzlu s hodnotou prvku v 

posledním listu haldy (uzel s nejvyšším indexem).

• Haldu o tento list zkrátíme. (Vyřadíme ho z haldy.)
• Pro nový prvek v kořeni ověříme, zda splňuje podmínku haldy.
• Pokud ne, vyměňujeme prvky mezi uzly a jejich následníky tak dlouho, 

až všechny uzly splňují podmínku haldy.

• Vezmeme další uzel v pořadí (s druhým nejvyšším indexem) a 

vyměníme jeho hodnotu s hodnotou v kořenovém uzlu.

Vlastní třídění

• Opět haldu zkrátíme a ověříme zda prvek v kořenu splňuje podmínku 

haldy. Pokud není splněna podmínka haldy, provedeme výměny.

• Každým krokem se halda zkrátí o jeden prvek, až nakonec halda 

obsahuje pouze kořenový uzel. Tím proces třídění končí.

• Odebírané hodnoty z haldy tvoří setříděnou posloupnost.

Příklad činnosti algoritmu třídění pomocí 
haldy
• Je dána posloupnost čísel: 7 1 2 8 2 4 5 3 1 9 .
• Popište konkrétně jednotlivé kroky třídění a pro každý krok nakreslete 

aktuální stav haldy.

• (Uvažujme vzestupné třídění.)

Implementace haldy

• Haldu lze implementovat jako strom

• Uzel obsahuje ukazatele na své následovníky.
• Zbytečně složité a málo efektivní.

• Vzhledem k pravidelnému tvaru může být halda implementována