11-Trideni_halda_stromy

𝑛 = 1 + 21 + 22 + ⋯ + 2ℎ−1 + 2ℎ = 1 ∙

2ℎ+1 − 1

2 − 1

= 2ℎ+1 − 1

(jedná se o součet ℎ + 1 členů geometrické řady s kvocientem 2 a 
prvním členem 1).

• Naopak pokud poslední vrstva obsahuje pouze jeden uzel, celkový 

počet uzlů stromu bude: 

𝑛 = 1 + 21 + 22 + ⋯ + 2ℎ−1 + 1 = 1 ∙

2ℎ − 1

2 − 1

+ 1 = 2ℎ

Vztah mezi počtem uzlů a výškou binárního 
vyváženého stromu
• Počet uzlů 𝑛 binárního vyváženého stromu o výšce ℎ se musí 

pohybovat v rozmezí: 2ℎ ≤ 𝑛 ≤ 2ℎ+1 − 1.

• Postupnými úpravami dostaneme:

𝑛 ≤ 2ℎ+1 − 1, 2ℎ ≤ 𝑛

𝑛 + 1 ≤ 2ℎ+1
𝑛+1

2

≤ 2ℎ ≤ 𝑛

𝑙𝑜𝑔2

𝑛+1

2

≤ ℎ ≤ 𝑙𝑜𝑔2 𝑛

𝑙𝑜𝑔2 𝑛 + 1 − 1 ≤ ℎ ≤ 𝑙𝑜𝑔2 ℎ

Třídění s využitím haldy

Halda

• Speciální typ vyváženého binárního stromu, u kterého prvky ve všech 

uzlech splňují podmínku haldy:

• Hodnota prvku v uzlu předchůdce (a) nesmí být menší než hodnota prvku v 

jeho následovnících (b, c)  (pokud následovníci existují). 

b

a

c

𝑎 ≥ 𝑐

𝑎 ≥ 𝑏

Symbolická značka pro haldu

Algoritmus třídění pomocí haldy

• Algoritmus má dvě fáze

• Vytvoření haldy
• Vlastní třídění

Vytvoření haldy

• Z počtu prvků 𝑛 tříděného pole stanovíme výšku haldy: ℎ = 𝑙𝑜𝑔2 𝑛
• Sestavíme binární strom výšky ℎ s 𝑛 uzly a naplníme ho tříděnými 

prvky (do každého uzlu dáme jeden tříděný prvek).

• Odspodu procházíme nelistové uzly a ověřujeme, zda splňují 

podmínku haldy vzhledem ke svým následníkům. 

• Ověřujeme, zda hodnota prvku v uzlu není menší než hodnoty prvků v jeho 

následnících.

Vytvoření haldy

• Pokud uzel nesplňuje podmínku haldy, musíme provést výměnu 

prvků.

b

a

c

→

𝑎 < 𝑏

𝑏 ≥ 𝑐