Heapsort

Vu Wikipedia
Wiesselen op: Navigatioun, sichen

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 ëm een in-place, net-stabilt Zortéierverfahren, dat op der Datestruktur Heap operéiert.

Heaps[änneren | Quelltext änneren]

Een Heap an deen entspriechenden Tableau dozou

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:

key(v)\leq key(father(v))

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 um Level k oder k+1 (k\in\mathbb{N}), 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)

Funktiounsweis[änneren | Quelltext änneren]

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 dacks 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 hiergestallt 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.

Opbauphas[änneren | Quelltext änneren]

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éier oprifft, sou gëtt de Bam Level fir Level an een Heap verwandelt.

Selektiounsphas[änneren | Quelltext änneren]

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 hiergestallt ginn. Ass dës dann nees hiergestallt, sou vertauscht een nees dat éischt Element mat deem leschten (nei Positioun) a sou weider, bis ee vir ukomm ass.

Algorithmus[änneren | Quelltext änneren]

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

Opbauphas

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

Selektiounsphas

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

Lafzäit[änneren | Quelltext änneren]

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 Selektiounsphas brauch am schlëmmste Fall (Worst Case) awer iwwerlineär Zäit (O(n\log n)). Also kann Heapsort een Tableau vun der Gréisst n am schlëmmste Fall an O(n\log n) Zäit zortéieren.

Den allgemengen Zortéierproblem huet eng Komplexitéit vun \Omega(n\log n), sou datt dës Lafzäit déi bescht ass, déi ee mat engem allgemengen Zortéierverfahren erreeche kann.

Literatur[änneren | Quelltext änneren]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. MIT Press, 1990, 2. Oplo Sept. 2001, 1.184 Säiten.

Um Spaweck[änneren | Quelltext änneren]

Commons: Heap sort – Biller, Videoen oder Audiodateien