Heapsort

Vu Wikipedia, der fräier Enzyklopedie.

Heapsort ass ee séiert allgemengt Zortéierverfahren, dat 1964 vum Robert W. Floyd a J.W.J. Williams entwéckelt ginn ass. Et handelt sech dobäi em een in-place, net-stabilt Zortéierverfahren, dat op der Datestruktur Heap operéiert.

Inhaltsverzeechnes 1 Heaps 2 Funktiounsweis 2.1 Opbauphas 2.2 Selektiounsphas 3 Algorithmus 4 Lafzäit 5 Literatur

[Änneren] Heaps

Een Heap ass eng Bamstruktur, där hir Kniet mat Schlësselen (Zuelen) markéiert sinn, sou datt fir all Knuet v (mat Ausnam vun der Wuerzel) gëllt:

De Schlëssel vu v ass méi kleng oder gläich wéi de Schlëssel vum iwwergeuerdnetem Knuet vu v. Et léisst sech liicht feststellen, datt an der Wuerzel vum Bam de Maximum vun all de Schlëssele gespäichert muss sinn.

Heapsort benotzt binär ausgeglachen Heaps. Bei binären Heaps huet all Knuet entweder zwee oder null Kanner, bis eventuell op een, dee kann nëmmen ee Kand hunn. Bei ausgeglachen Heaps stinn d'Blieder (Kniet ouni Kanner) all op dem Level k oder k + 1 (), woubäi se um k + 1-Level souwäit lénks wéi méiglech stinn. Mat dëser Eegeschaft léisst sech een Heap ganz einfach an een Tableau A iwwerdroen.

Et gëllt also:

• D'Wuerzel vum Heap ass A[1]
• D'lénkst Kand vun A[i] ass A[2i]
• D'rietst Kand vun A[i] ass A[2i + 1]
• Den iwwergeuerdnete Knuet vun A[i] ass A[i / 2] (ofgerënnt)
• Een Element A[i] ass ee Blat, wann 2i > n gëllt. (n ass d'Unzuel vun den Elementer)

[Änneren] Funktiounsweis

Heapsort besteet aus zwou Phasen:

• der Opbauphas, déi een Tableau A[1..n] an een Heap verwandelt an
• der Selektiounsphas, déi eng Zortéierung duerch Maximumsauswiel duerchféiert.

Souwuel d'Opbauphas als och Selektiounsphas benotzen eng Funktioun, déi oft Heapify genannt gëtt an déi der Reconstitutioun vun der Heap-Eegeschaft déngt. Dës Funktioun setzt allerdéngs viraus, datt d'Ennerbeem vun engem Element schonn Heaps sinn, awer d'Element selwer méi kleng ka si wéi seng zwee Kanner an domat Heap-Eegeschaft verletzt. D'Iddi ass et elo, fir dëst Element erofwanderen ze loossen, bis d'Heap-Eegeschaft nees hirgestallt ass. Dobäi gëtt de Maximum vun den zwee Kanner vun dësem Element gesicht. Falls d'Element méi grouss oder gläich dem Maximum vun den zwee Kanner ass, ass ee fäerdeg. Am anere Fall vertauscht een de Maximum mam Element an et mécht ee bei der Positioun drënner weider.

[Änneren] Opbauphas

Viraussetzung, datt een een Tableau mat zortéierbare Wäerte mat Heapsort zortéiere kann, ass, datt dësen een Heap representéiert. Andeems een d'Funktioun Heapify an enger bottom-up Manéier benotzt, kann een een Tableau an een Heap verwandelen. Well d'Blieder automatesch d'Heap-Eegeschaft erfëllen (well se keng Kanner hunn), fänkt ee bei deem iwwergeuerdnetem Knuet vum leschte Blat mam Opbau vum Heap un. Dëse Knuet ass op der Positioun n / 2 (ofgerënnt) ze fannen. Leeft een elo vun deem Knuet aus erop bis zur Wuerzel, andeems een Heapify-Funktioun all kéiers oprifft, esou gëtt de Bam Level fir Level an een Heap verwandelt.

[Änneren] Selektiounsphas

D'Selektiounsphas féiert déi eigentlech Zortéierung duerch Maximumsauswiel duerch. Well an engem Heap de Maximum ëmmer an der Wuerzel gespäichert ass, also op der éischter Positioun vum Tableau steet, vertauscht een einfach dat éischt Element mat dem leschten a verkierzt den Tableau hannen ëm eng Positioun. De Maximum steet elo op der gewënschter Plaz. Duerch d'Vertauschung ass d'Heap-Eegeschaft awer verletzt ginn a muss nees mat der Heapify-Funktioun hirgestallt ginn. Ass dës dann nees hirgestallt, esou vertauscht een nees dat éischt Element mat deem leschten (nei Positioun) an esou weider, bis ee vir ukomm ass.

[Änneren] Algorithmus

De folgende Pseudocode stellt eng Implementéierung vum Algorithmus dur:

Funktioun Heapify als rekursiv Variant

function Heapify(i,n)
        l := 2i    // lénkst Kand
        r := l+1   // rietst Kand
        m := i
        if(l<=n and A[l]>A[m]) then
                m := l
        fi
        if(r<=n and A[r]>A[m]) then
                m := r
        fi
        if(m!=i) then
                t := A[i]          // Vertauschung
                A[i] := A[m]       // vun A[i]
                A[m] := t          // mat A[m]

                Heapify(m,n)       // rekursiven Opruff
        fi
end

Opbauphase

for i := floor(n/2) downto 1 do
        Heapify(i,n)
od

Selektiounsphase

r := n
while r>1 do
        t := A[1]          // Vertauschung
        A[l] := A[r]       // vun A[1]
        A[r] := t          // mat A[r]

        r := r-1
        Heapify(1,r)
od

[Änneren] Lafzäit

Et kann ee beweisen, datt den Opbau vun engem Heap a lineärer Zäit (Landau-Notatioun: O(n)) ze realiséieren ass. D'Zortéierung an der Selektiounsphase brauch am schlechteste Fall (Worst Case) awer iwwerlineär Zäit (O(nlogn)). Also kann Heapsort een Tableau vun der Gréisst n am schlechteste Fall an O(nlogn) Zäit zortéieren.

D'allgemengt Zortéierproblem huet eng Komplexitéit vu Ω(nlogn), sou datt dës Lafzäit déi bescht ass, déi een mat engem allgemengen Zortéierverfahren areeche kann.

[Änneren] Literatur

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. MIT Press, 1990.