16. óra
Címkék > Óra
Elmélet > Algoritmusok > Rendezések

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)
    //kezdeti kupac felépítése
    Ciklus i := N/2-től 1-ig
        kupacol(T,N,i)
    Ciklus vége
    //maximális elemek helyretétele egymás után
    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