16. óra
(Peregi Tamás, 2008. 02. 04.)
Kupacrendezés
Egy T[] tömbben lévő elemeket rendezzük
$O(n\log (n))$ lépésben.
A kupac
A kupac egy majdnem teljes bináris fa, amelynek csúcsai tárolják a
tömb elemeit. A kupac egy csomópontjában lévő érték mindig nagyobb
(nem kisebb), mint a két gyermekcsomópont értéke.
Kupac egy "rossz" elemének helyreküldése
Ha a T[k] alatti két részgráf már kupac, akkor a T[k..N]
résztömböt alakíthatjuk kupaccá ezzel az eljárással.
eljárás kupacol(T, N, k)
E := T[k]
apa := k
fiu := 2*apa
Ha fiu < N és T[fiu+1]>T[fiu] akkor
fiu++
Elágazás vége
Ciklus amíg fiu <= N és T[fiu] > E
T[apa] := T[fiu]
apa := fiu
fiu := 2*apa
Ha fiu < N és T[fiu+1]>T[fiu] akkor
fiu++
Elágazás vége
Ciklus vége
T[apa] := E
eljárás vége
Kupacrendezés
eljárás rendez(T,N)
Ciklus i := N/2-től 1-ig
kupacol(T,N,i)
Ciklus vége
Ciklus i:=1-től (N-1)-ig
csere(T,1,N-i+1)
kupacol(T,N-i,1)
Ciklus vége
eljárás vége
