BPC-ALD - Skripta_rev2019_2
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
tento list zkrátíme.
Nyní je nutno vyměnit hodnoty postupně mezi uzly mezi u0 a u2 a uzly u2 a u6.
− 45 −
Hodnotu v kořenu vymění s hodnotou v posledním listu u6 haldy a haldu o tento list zkrátíme.
Nyní je nutno vyměnit hodnoty mezi uzly u0 a u2 a uzly u2 a u5 .
Hodnotu v kořenu vymění s hodnotou v posledním listu u5 haldy a haldu o tento list zkrátíme.
Následuje výměna hodnot postupně mezi uzly mezi u0 a u1 a uzly u1 a u3.
Hodnotu v kořenu vymění s hodnotou v posledním listu u4 haldy a haldu o tento list zkrátíme.
− 46 −
Atd.
Složitost metody Vezměme nejprve složitost vytvoření haldy. Při něm procházíme jednotlivé jeho nelistové uzly,
srovnáváme prvky v něm uložené s následníky a případně provádíme přesuny. Srovnání je
v každém uzlu nutné provést dvě - se dvěma následníky (má-li uzel oba následníky). Následně
proběhne případný přesun. Vezměme ten nejhorší případ, kdy srovnání a přesuny proběhnou od
nejhornějšího uzlu (kořene) až po ten nejspodnější nelistový uzel. Jde celkem o 3
∗h operací (3
operace v každém uzlu: 2 srovnání + 1 přesun), kde h je výška stromu. Výška binárního
vyváženého stromu logaritmicky závisí na počtu uzlů (prvků). Tedy pro každý probíraný
nelistový jeden uzel má v nejhorším případě (a i v průměrném případě) logaritmickou složitost.
Když ji vynásobíme počtem
2
n
uvažovaných nelistových uzlů, dostaneme složitost vytvoření
haldy
Θ(n∗log(n)).
Zbývá stanovit složitost fáze vlastního třídění. Ta je hlavně určena složitostí operací srovnání a
případných výměn, které následují po vzájemné výměně prvků mezi kořenem a posledním
listem ve stávající haldě a zkrácením haldy o tento list. Opět to vyžaduje 2 srovnání a 1 přesun
na každý nelistový uzel (nebo 1 srovnání, pokud uzel má jen jednoho následníka). Tedy
maximálně 3