Algoritmus řazení slučov/Ením (funke, verze)
mergeSort : :    [Int] —>- [Int]
mergeSort  []     = [] mergeSort  [x]    = [x]
mergeSort s       =   merge (mergeSort u)  (mergeSort v)
where (u,v) = splitAt (n cdivc 2) s n        = length s
merge s [] s merge [] t = t
merge (x:u)  (y:v)    =   if x < y   then   x : merge       u (y:v)
else   y : merge (x:u) v
47
Příklad:
ms [4,3,1,6,7,2,8,5]
mr (ms  [4,3,1,6])    ( ms [7,2,8,5])
mr (mr   (ms [4,3])   (ms [1,6]) )      ( mr   (ms [7,2])   (ms [8,5]) )
mr (mr (mr (ms [4] ) (ms [3] ) ) (mr (ms [1] ) (ms [6] ) ) )   (mr (mr (ms [7] ) (ms [2] ) ) (mr (ms [8] ) (ms [5] ) ) )
mr (mr   ( mr   [4]    [3] )   ( mr   [1]    [6] ) )      ( mr   ( mr   [7]    [2] )   ( mr   [8]    [5] ) )
mr Ur [3,4]    [1,6])      ( mr [2,7] [5,8])
mr [1,3,4,6] [2,5,7,8] [1,2,3,4,5,6,7,8]
_J
Věta:   Nechť In — Ouť\e množina všech seznamů (posloupností) celých čísel, cp(s) = s je konečný, ^(s, í) = t je permutací seznamu s a t je neklesající. Pak mergeSort je tot/Elě korektní vzhledem k podmínk/Em^, ip.
Lemma:   Časov/E složitost pomocn0 funkcmerge je Tmerge G O (n). Věta:   Časov/E složitost funkcanergeSort je TmergeSort E 0(n - log n).
Důkaz tot/Elní korektnosti: Konvergence i parci/Elní koréikost se dok/Eže indukcí podle d0lky seznamu s, parci/Elní korektnost pomocn0 funkceierge se dok/Eže indukcí podle soětu d0lek obou slučovaných seznamů.
Line/Erní složitost funkcanerge je zřejm/E: konstantní d0lka porovn/Ení áipojení menšího prvku na zač/Etek posloupnosti se dohromady provede tolikr/Et, kolik jeoučet d0lek obou vstupních posloupností (argumentů funkce merge).
Odvození složitosti funkce mergeSort je na n/Esledujících stran/Ech.
Algoritmus řazení slučov/Ením (imp. verze)
type Elem = Integer;   Posl = array [1..MAX] of Elem; procedure mergeSort (n:Integer; var A:Posl); var B : Posl; { pomocné pole }
procedure msort (p,r:Integer); { seřadí pole od p do r } var q : Integer; begin if p < r then begin
q := [(p+r)/2j ; msort (p,q) ; msort (q+l,r) ; merge (p,q,r) end
50
procedure merge (p,q,r:Integer);
{ sloučí úsek A[p] , . . . ,A[q] s úsekem A[q+1] ,. . .,A[r] }
var i,j  : Integer;
begin
i := p ;    j  := q + 1 ; for k := p to r do
if (i<q) && (j<r) && (A[i] <A[j])   || (j>r)
then        begin B[k]  := A[i]  ; i := i+1 end else if (i<q) && (j<r) && (A[i]>A[j])   || (i>q) then        begin B[k]  := A[j]  ; j  := j+1 end ; for k := p to r do   A[k]  := B[k] end
begin { mergeSort }
msort (l,n) end     { mergeSort }
Pozn/Emka: Podmíněný příkaz v těle cyklu for procedury merge lze ekvivalentně zapsat kratčeji takto (dokažte)
if ( i<q ) && then begin else begin
( j>r | | A [i] B[k] := A [i] ; B[k]   := A[j] ;
<A[j] ) i := i+1 end j  := j+1 end ;
Časov/E složitost algoritmiřazení slučov/Ením
Analýza nejhoršího případu
Pro danou velikost n je d0lka výpočtu vždy stejn/E.
Časov/E složitost
T(l) = a
T{n) = b + T{\n/2\) +T([n/2\) + D{n),   D e 6>(n)
T'(l) =a
T'(n) = b + 2T'(n/2)+n-c,   T' G O (T).
Analýza nejhoršího případu je zde trivi/Elní: pro každou vstupní posloupnost ôGfy n algoritmus děl/E stejnou pr/Eci. Pro složitosT : N —)> N tedy platí, že T(n) je rovno d0lce výpočtu na //bovo//70vstupní posloupnosti d0lkyn.
Je-li n < 1, pak T(n) = a, kde a je konstanta.
Je-li n > 1, pak T(n) = b + T(\n/2]) +T([n/2\) + D(n), kde D je složitost zbytku těla procedury msort (bez rekursivního vol/Ení), tedy zejm0na pomocn0 procedunjierge.
Procedura merge je tvořena cyklem s pevným počtem opakov/Ení^i), takže D(n) = c • n, kde c je konstanta. Tedy D G G (n).
Protože    /2j a [n/2] se liší nejvýše o 1 (tj. o konstantu), můžeme tento rozdíl zanedbat. Takto upraven/E funkceZ1' roste stejně rychle jako T: T'(l) =a
T'(n) = 6 + 2T'(\n/2~\) + n -c,   T' e G (T).
Pro několik hodnot n dost/Ev/Eme
T'(l) = a
Tf(2) = & + 2-T'(l) + 2c = 2a + b + 2c
T'(4) = fc + 2-T'(2)+4c = 4a+ 36 +8c
T'(8) = & + 2-T'(4)+8c = 8a + 7& + 24c
T'(16) = & + 2-T'(8) + 16c = 16a+15& + 64c
T'(32) = 6 + 2-T'(16) + 32c = 32a+ 31&+160c
Všimneme-li si hodnot T' na mocnin/Ech dvou, můžeme vyslovit tvrzení Věta:   Pro každ0& G N je
T'{2k) = 2ka + (2k - l)b + 2kkc
Vyj/Eateno pomocí n:
Tf(n) = a - n + b - (n — 1) -\- c • n log2 n
Protože line/Erní funkcea-n, b-n rostou nejvýše tak rychle jako n • log n, tak T' G O {n log n). T roste stejně rychle, takže i TG (9(n log n).
54
Rovnosti T(l) = c
T{n) = 2T(\n/2]) + ďn
jsou speci/Elním pípadem situace, v níž je
T(l) = c
T(n) = a T([n/6]) + f(n), kde a>l,6>l,c>0a/je kladn/E funkce. Napíklad pro algoritmus řazení slučov/Ením jea = 2, b = 2, / G (9(n), tedy případ „2" n/Esledující éty.
Věta:   Nechť a > 1, 6 > 1, / je kladn/E funkce a T(l) = c
T(n) = a • T (£) + /(n) Potom:
1. Pokud / G 0(nlogř>a~£) pro nějak0£ > 0, pakT G <9(nl09ř>a).
2. Pokud / G 6>(rilogř>a), pakT G <9(nlogř>alogn).
3. Pokud / G i?(nlogř>a+£) pro nějak0£ > 0 a pokud a • f(n/b) < d • f{n) pro nějak0 d < 1 a skoro všechna n, pak T G 0(f(n)).
Dolní odhad složitosti řadicích algoritmů
Def:   Asociativní řadicí algoritmus je algoritmus, jehož množinu přípustných vstupních dat tvoří všechny konečn0 posloupnosti celýchčísel, a takový, že jeho výsledkem je neklesající permutace vstupní posloupnosti.
Pozn/Emka: Asociativní řadicí algoritmus tedy nemůže předpokl/Edat nic o velikosti řazených prvků a jedinou možností testov/Ení je srovn/Evatrpky mezi sebou.
Věta:   Každý sekvenční asociativní řadicí algoritmus m/E složitost vi?(n log n).
Pozn/Emka: Věta řík/E, žedolní odhad (časov0) složitosti probl0mu asociativního řazení je v množině Í2(n log n). Protože však zn/Eme konkr0tníadicí algoritmy s touto složitostí, vidíme, že tento odhad je dokonce těsný: Časov/E složitost probl0mu asociativního řazení je v množině 0{n log n).
Např. složitost řazení vkl/Ed/Ením, výfrem, bubl/Enírrči rozdělov/Ením je
0{n2) C Q {n log n), složitost řazení slučov/Enírrči haldou je G(n log n) C i? (n log
Pro určení složitosti uvažujeme z/Epis algoritmu v jednoduch0m fioikcion/Elním nebo imperativním jazyce, tj. ekvivalentní sekvenční implementaci RAMem.
Důkaz Věty o dolním odhadu složitosti
Bez oejmy na obecnosti můžeme pedpokl/Edat, že prvkyřazen0 posloupnosti jsou navz/Ejem různ0: chceme-li nejhorší případ, musíme seřazovat co nejvíce prvků. Dokonce se můžeme omezit jen na permutace množiny {1,..., n}: asociativní algoritmus si vším/E jen srovn/Ení dvojic prvků.
Poněvadž existuje celkem n! možných permutací a pro každou takovou permutaci na vstupu musí podle t0hož algoritmu proběhnout jiný výpočet, existuje aspoň n! různých výpočtů. Ve všech těchto výpočtech je aspoň n! — 1 bin/Erních testů, jejichž výsledky odliší jednotliv0 výpočty. Ale to znamen/E, že vnejdelším výpočtu (jde n/Em o nejhorší pípad) musí být aspoň |_log2 n!J testů. Pro složitost T /cazc/0/7oalgoritmu tedy musí platit T(n) > |_log2 n\\. To znamen/E, žeT G i?(log n\) = Q{n log n)
Cvičení:   V důkazu věty o dolním odhadu složitosti řadicích algoritmů se mlčky předpokl/Ed/E, že složitost jednoho porovn/Ení dvóísel ai a a j je konstantní. Můžete uv0st lepší (realističtější) odhad časov0 složitosti jednoho porovn/Ení?
Cvičení:   Ukažte, že log (n • log n) G (9 (log n).
Cvičení:   Uv/Ežíme-li realistickou složitost jednoho porovn/Ení, j^kvyjde dolní odhad složitosti řadicích algoritmů? Je v rozporu s dok/Ezanou étou? Je jejím zesílením?
Algoritmus řazení rozdělov/Ením
(funkcion/Elní verze)
quicksort  ::   [Int] —> [Int] quicksort  []       = []
quicksort (p:t) =   quicksort It ++ [p] ++ quicksort ge
where It = [ x | x-<—t, x<p ] ge = [ x | x«— t, x>p ]
Věta: Nechť In — Ouť\e množina všech seznamů (posloupností) celých čísel, cp(s) = „s je konečný",
ip(s, ť) = „t je permutací seznamu s a t je neklesající".
Pak quicksort je tot/Elě korektní vzhledem k podmínk/Em^, ip.
Věta:   Časov/E složitost algoritmuquickSort je v 0(n2).
Důkaz korektnosti: Konvergence i parci/Elní korektnost seuk/Eže indukcí vzhledem k d0lce seznamu s.
Řazení rozdělov/Ením (imperativní verze)
type   Element = Integer;
Posl = array [1..MAX] of Element;
procedure Quicksort (n:Integer, var A:Posl);
procedure Q (l,r:Integer); var p: Integer;
begin if l<r then begin p := Part (l,r);
Q (l.p-l);    Q (p+l,r)
end
end;
procedure Part (1,r:Integer); var i,j: Integer; x,y: Element; begin x := A[r];    i := 1 - 1; for j:=1 to r-1 do
if A[j] <x then begin i := i+1;
y := A[i];    A[i]   := A[j] ;    A[j]   := y;
end;
y := A [i+1];    A [i+1]   := A[r] ;    A[r]   := y Part := i + 1
end;
begin   Q (l,n) end
Řazení rozdělov/Ením (modif. imp. verze)
type   Element = Integer;
Posl = array [1..MAX] of Element;
procedure Quicksort (n:Integer, var A:Posl);
procedure Q (l,r:Integer); var p: Integer;
begin if l<r then begin p := Part (l,r);
if p-l<r-p then begin Q (l,p-l);    Q (p+l,r) end else begin Q (p+l,r);    Q (l,p-l) end
end
end;
procedure Part (1,r:Integer); var i,j: Integer; x,y: Element; begin x := A[r];    i := 1 - 1; for j:=1 to r-1 do
if A[j] <x then begin i := i+1;
y := A[i];    A[i]   := A[j] ;    A[j]   := y;
end;
y := A [i+1];    A [i+1]   := A[r] ;    A[r]   := y Part := i + 1
end;
begin   Q (l,n) end
58
Věta:   Algoritmus řazení rozdělov/Ením m/E složitost v množen0(n ).
Pozn/Emka: Průměrn/E30\Wa výpočtu podle algoritmu řazení rozdělov/Ením (t průměrn/Er\ebo oček/Evan/Easov/E složitošf je v množině 0(n log n).
Důkaz věty o kvadratick0 složitosti: Není ižk0 zjistit, že d0lka výpótu cyklu (repeat) je c • n (cel0 pole se projde jedním průchodem a výměna prvků trv/E konstantní dobu).
Označíme-li T{n) složitost seřazení pole d0lkyn, dostaneme
T{n) = c - n + max{T(g) + T(n — q — 1) |0<g<n}
Při nevyv/Ežen0měllení posloupnosti na podposloupnosti d0lekn — 1, 0 je d0lka výpočtu kvadratick/E. TedyT G Q{n2). Ale výraz T(q) + T(n — q — 1) nabude maxima pro q = 0 nebo q = n — 1 (o tomto případu víme, že je kvadratický) - druh/E derivaceT(n) vzhledem ke q pro kvadratický odhad T(n) < cn2 je kladn/E. Dohromady, T G ^(n2), T G 0(n2), tj. T G <9(n2).
Neform/Elní zdůvodění pozn/Emky o průnšrn0 složitosti:
Při každ0m vyvol/Ení procedury) se posloupnost d0lkyn rozdělí na dva oeseky ô0\e\q a n — q — 1. Předpokl/Ed/Eme-li rovnoěnrn0 rozloženíčísel (položek) v seřazovan0 posloupnosti, pak pravděpodobnost, že q < rn, je rovna číslu r, 0 < r < 1. Tedy pravděpodobnost, že se při výpočtu „nepřízniv/E" hodnota hraniceg vybere ve významn0m počtu případů, kles/E sčíslem r k nule. Proto stačí uvažovat jen případy, kdy se posloupnost dělí na oeseky d0lekš1ších než n/ro pro nějak0 pevndro > 0 (ostatní případy mají nevýznamnou pravděpodobnost). Ale pak je největší hloubka zanoření rovna log j^n = — logr n. Součet d0lek sesazovaných ceseků v každ0 hloubce je nejvýše^, takže
průměrn/Rji0\Wa výpočtu je nejvýše —c • n • logron, tedy v 0(n log n). D/Ele se snadno ověří (například pro ro = 1/2), že n log n je i dolním odhadem, takže průměrn/E d0lka výpočtu je v 0(n log n).
Prostorov/E složitosřadicích algoritmů
Definujeme prostorovou složitost algoritmu analogicky jako časovou složitost, ale za míru složitosti místo počtu kroků výpočtu zvolíme maxim/Elní množství panšti, kter/E bude během výpočtu obsazena.
Def: Prostorov/E složitost algoritmuA je funkce, kter/E pro každou velikost vstupních dat je rovna velikosti obsazen0 parrěti při výpočtu, jenž t0to parrěti spotřebuje nejvíc.
Pozn/Emka: Označíme-li p(A, ax) množství paměti spotřebovan0 výpočtem podle algoritmu A z poč/Etěního stavu ax (odpovídajícího umístění dat x na vstupu), potom prostorov/E složitost algoritmuA je
Sa(^) — max{p(A, ax) | \x\ — n}
60
Prostorov/E složitost všech zrrfíiovaných řadicích algoritmů je line/Erní, tj^S G O (n). Důvod je ten, že souč/Estí dat, s nimiž algoritmus pracuje, je samaazen/E posloupnost, a ta m/E d0lkun. Ostatní data (mimo tuto posloupnost, tj. „extrasekvenční") mají v uv/Eěných algoritmech velikost nejvýše 0(n).
Def:   Zavedeme extrasekvenční prostorovou složitost řadicího algoritmu jako funkci
zobrazující d0lky vstupní posloupnosti na velikost paměti obsazen0 pi výpočtu
v nejhorším případě, ale nezapočít/Ev/Eme paět' obsazenou seřazovanou posloupností.
Řadicí algoritmy, kter0 mají extrasekvenční prostorovou složitost konstantní, se nazývají in situ.
Řazení rozdělov/Ením není/V? situ.
Věta:   První varianta algoritmu quickSort m/E extrasekveční prostorovou složitost 0(n), druh/E (modifikovan/E) varianta tohoto algoritmu m/E extrá&©nční prostorovou složitost (9 (log n).
J
61
Pozn/Emka: Hovořit o řadicích algoritmech, zda jsou in situ, a zav/Eět jejich extrasekvenční prostorovou složitost m/E praktický význam jen tehdy, je-lposloupnost reprezentov/Ena polem a uložena v souvisl0m ceseku pareti. Při jiných datových reprezentacích posloupnosti (např. seznamem) se extrasekvenční prostorov/E složitost nezav/Edí.
Řazení haldou
Def:   Nechť K je oeplrě uspoř/Edan/E množina XzMíčů (typicky množina čísel s přirozeným uspoř/Ed/Enírr<). Bin/Erní hald^e bin/Erní strom, jehož uzly jsou ohodnoceny prvky množiny K, a který splňuje tyto vlastnosti:
1. D0lky všech větví se liší nejvýše o 1: mají Ó0\kuk, případně k — 1. Číslu k pak V\k/E\r\ehloubka haldy.
2. Hodnoty uzlů na každ0 větvi jsou vzestupně (sestupně) uspoř/Ed/Eny.
Jsou-li hodnoty uzlů na každ0 větvi seřazeny vzestupně (čím d/Ele od kéene, tím větší hodnoty), je v kořenu haldy nejmenší prvek. Hovoříme pak o minimov0ha\óě (min-heap).
Jsou-li hodnoty uzlů na každ0 větvi seřazeny sestupně (čím d/Ele od kčene, tím menší hodnoty), je v kořenu haldy největší prvek. Hovoříme pak o maximov0ha\óě (max-heap).
___J
Ve funkcion/Elní implementaci algoritmiřazení haldou, kde se pracuje s explicitní haldou (datovou strukturou bin/Erní strom), použijeme minimovou laldu. Naopak v imperativní implementaci, kde se pracuje s implicitní haldou (reprezentovanou polem), je výhodnější použít maximovou haldu.
Operace s bin/Erní haldou
data Heap = Empty I Node Elem Heap Heap
Z/Ekladní operace - konstruktory a selektory - mají konstarrhí složitost.
Konstruktory Empty : Heap
Node : Elem —» Heap —» Heap —» Heap Selektory
rootVal : Heap —-> Elem lef tHeap : Heap —■> Heap rightHeap : Heap —■> Heap
isEmpty : Heap —> Bool
Další operace pro pr/Eci s bin/Erní haldou
Vyhled/Ení minim/Elního prvku (v minimov0 hátyJ minH : Heap —■> Elem minH = rootVal (složitost 0(1))
Odstranění minim/Elního prvku (z minimov0 haldy) extractMinH : Heap —■> Heap (složitost 0(log ri))
Odstranění maxim/Elního prvku (z maximovO haldy) extractMaxH : Heap —■> Heap (složitost 0(log ri))
Přid/Ení prvku
insertH : Elem —> Heap —> Heap (složitost (9 (log ri))
Odstranění prvku
removeH : Heap —> Heap —■> Heap (složitost (9 (log n))
Věta:   Nepr/Ezdn/E bin/Erní halda mauzlech m/E hloubkuLlog2^J ■ Důkaz indukcí podle n.
Def: Bin/Erní strom, v jehož každ0m podstromu se poet uzlů Iev0ho a prav0ho podstromu liší nejvýše o jednu, se nazýv/Euzlově vyv/Eženýom/Emí strom.
Věta:   Každý uzlově vyv/Ežený bin/Erní strom je haldou (až na ohodnocení uzlů).
Důkaz: Je třeba dok/Ezat, že d0lky všeché^tví uzlově vyv/Ežen0ho stromu se liší nejvýše o jednu.
Předpokl/Edejme sporem, že tvrzení neplatí, aT je nejmenší strom, který tvrzení porušuje. Tedy v každ0m podstromu stromuT se počet uzlů vlevo a vpravo liší nejvýše o jednu, ale existují zde dvě větve d0lekm a k, přičemž m > k + 2. Z minimality stromu T plyne, že jedna z těchto dvou větví, řekněme ta delší, d0lkym, leží v Iev0m podstromuX/ stromu T, a druh/E, kratší, o0\Wjz, v prav0m podstromuTr stromu T. Navíc, rovněž z minimality, všechny větve jdoucí do T\ mají d0lkum nebo m — 1, všechny větve jdoucí do Tr mají d0lku& nebo k + 1. To znamen/E, žeZ] m/E aspá o dva uzly víc než Tr. Ale podle předpokladu věty m/E nejvýše o jeden uzel více, což je spor.
Algoritmus řazení bin/Erní haldou (funkcion/Ení verze)
data Heap   =   Empty    I    Node Int Heap Heap
insHeap : : Int —>• Heap —>• Heap insHeap u Empty =   Node u Empty Empty
insHeap u (Node v p q)   =   if u > v   then   Node v (insHeap u q) p
else   Node u (insHeap v q) p
toHeap : :  [Int] —>• Heap toHeap s = foldr insHeap Empty s
toList : : Heap —>• [Int] toList Empty = []
toList (Node x 1 r) = x : merge (toList 1)  (toList r)
heapSort : :   [Int] —>> [Int] heapSort   =   toList   • toHeap
_J
68
Korektnost řazení haldou
Věta:   Algoritmus heapSort je tot/Elě korektní řadicí algoritmus.
Konvergence algoritmu je zřejm/E. Důkaz parci/Elní korektnosti vyplýv/E z n/EsledoJicí lemmat.
Lemma: Funkce toList vytvoří z haldy h seznam s týmiž prvky jako měla halda h, ale uspoř/Edaný vzestupe.
Lemma:   Je-li u číslo a h uzlově vyv/Ežen/E halda, paknsHeap u h je halda obsahující pr/Eé prvky z haldy h a prvek u.
Lemma:   Funkce toHeap vytvoří ze seznamu s haldu obsahující tyt0ž prvky jako seznam s.
Důkaz prvního lemmatu indukcí podle velikosti haldy.
Důkaz druh0ho lemmatu: indukcí podle počtu prvků v h se uk/Eže, že bin/Erní strom insHeap u h bude opět uzlově vyv/Ežený.
Podle věty o bin/Erních stromech vyv/Ežených vzhledem k přcbu uzlů bude výsledek opět halda.
Uspoř/Ed/Ení hodnot pod0ětví vyplýv/E z definice funkceinsHeap.
Třetí lemma indukcí podle d0lky seznamu a z definice kombin/Etnu f oldr. foldr insHeap Empty \_x\ 9X2 ,... ,xn] = insHeap X\ (insHeap X2 (• • • (insHeap xn Empty)...))
Složitost řazení haldou
Lemma:   Procedura insHeap m/E složitost vO(log n).
Důkaz: Funkce insHeap se rekursivně vyhodnotí pr/Eé tolikr/Et, jako je hloubka haldy. Ale ta je logaritmick/E vzhledem k potu jejích uzlů, jichž je vždy nejvýše n.
Věta:   Algoritmus řazení haldou m/E složitost v0(n log n).
Důkaz: Z předchozího lemmatu vyplýv/E, že složitost funkcetoHeap je v 0(n log n). Ve funkci toList je hloubka rekursivního zanoření logaritmick/E, protože seznamy se půlí. Složitost pomocn0 funkcemerge je line/Erní a oehrnn/E d0lka vyfia>všech vol/Ení
TL
funkce merge ve stejn0 hloubce k (tj. se stejně dlouhými seznamy) je —r • 2k = n.
2K
Funkce toList m/E tedy složitost tak0 \0(n log n). Celkem je tedy horní odhad složitosti funkce heapSort n log n, ale podle Věty o dolním odhadu složitosti řadicích je toto i dolním odhadem.
V imperativním algoritmu heapSort se použív/E maximov/E halda, tj. bin/Erní halda, kter/E m/E položky ve étvích seřazeny sestupně. Tedy největší položka je vždy v kořeni.
Jelikož algoritmus m/E haldu efektivě reprezentov/Enu polem, je zde výhodější uvažovat bin/Erní haldu nikoliv uzloé vyv/Eženou, ale naopak s levým podstromem ,$žším".
Def:    Vlevo zarovnan/E haldqe bin/Erní halda, jejíž všechny étve 60\kyk leží nalevo od větví d0lky/c — 1.
71
72
Věta:   Reprezentujme vlevo zarovnanou bin/Erní haldu nan uzlech posloupností hodnot jejích uzlů (ai,..., an) takto: a\ reprezentuje kořen haldy a je-li uzel u reprezentov/En prvkerra^ pak levý n/Esledník uzluu je reprezentov/En prvkem^ a pravý n/Esledník uzluu je reprezentov/En prvkerra2i+i. Pak posloupnost (ai,..., an) je haldou určena jednoznačně.
Věta umožňuje pracovat s vlevo zarovnanou bin/Erní haldou reprezentovanou v paměti polem. Vlevo zarovnan/E bin/Erní halda je tot0ž jako pole ropean0 „po vrstv/Ech".
73
Algoritmus řazení bin/Erní haldou (imp. verze)
type   Element = Int;
Posl = array [1..MAX] of Element;
procedure heapSort (n:Int, var A:Posl); var 1,r: Int;    x: Element;
procedure createHeap (l,r:Int);
{ vytvoření haldy A[l]...A[r] ze dvou podhald začínajících A[2*1] a A[2*1+1] } var i,j:Int; {pom. indexy}   y:Element; {zařazovaný prvek}   p:Bool; {sestupovat?} begin i := 1;    j  := 2*i;    y := A[i];   p := True; while   p   &&    (j<r) do   { sestupujeme }
begin if (j<r) && (A[j] < A[j+1]) then j:=j+l;
{ A[j] je teď větší z kořenů podhald pod A[i] } p := y<A[j];
if p then { A[j]>y, takže posuneme A[j] o patro výš } begin
A[i]   := A[j]; i := j;    j  := 2*i end
end;
A[i]   := y   { prvek y zařazen na své místo } end {createHeap};
74
begin {heapSort}
{ postupně vytvoříme haldu A [1],...,A[n] }
for 1 := n div 2 downto 1 do   createHeapd,n);
{ V kořenu (A[l]) je prvek s největším ohodnocením.} { Vyměníme ho s koncem pole, haldu zkrátíme } { a restaurujeme zařazením A[l] na správné místo } for r := n downto 2 do begin
x := A[l];    A[l]   := A[r] ;    A[r]   := x; createHeap (l,r-l)
end
end {heapSort};
Korektnost a složitost imperativního algoritmu heapSort
Věta:   Mějme vlevo zarovnanou bin/Erní haldu reprezentovanou poslopností (a/,..., ar) a nechť oba podstromy pod kořenem splňují podmínky haldy. Pak posloupnost (aj,..., a'r) ve stavu po provedení createHeap(a, Z, r) splňuje podmínky (vlevo zarovnan0) bin/Erní haldy.
Důkaz indukcí podle hloubky haldy.
Věta:   Provedení procedury heapSort (A) seřadí posloupnost A
Idea důkazu: Jednoprvkov0 podstromy reprezentovan0 drubu polovinou posloupnosti A jsou trivi/Elní podhaldy. První f/Eze algoritmu vytvflž těchto podhald větší podhaldy. Na konci první f/Eze je posloupnostA bin/Erní haldou.
Druh/E f/Eze algoritmu vytvbz haldy seřazenou posloupnost. To vyplýv/E z toho, že největší prvek haldy je vždy v jejím kořenu: největší prvky se skl/Edají na konec posloupnosti.
Věta:   Algoritmus řazení haldou konverguje.
Důkaz: Tvrzení věty vyplýv/E z koněn0 velikosti a hloubky haldy.
Věta:   Řazení haldou (imperativní algoritmus) m/E složitost v0(n log n).
Důkaz: První f/Eze (vytvoření haldy) m/E složitostO ^— log     , druh/E f/Eze m/E složitost
0(n log n), obě tedy dohromady 0(n log n).
Podle Věty o dolním odhadu složitosti musí být rovněž v (2{n log n).
Z obou odhadů pak plyne tvrzení.