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 (mat Ausnam vun der Wuerzel) gëllt:

De Schlëssel vu ass méi kleng oder gläich wéi de Schlëssel vum iwwergeuerdnetem Knuet vu . 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 oder (), woubäi se um -Level souwäit lénks wéi méiglech stinn. Mat dëser Eegenschaft léisst sech een Heap ganz einfach an een Tableau iwwerdroen.

Et gëllt also:

  • D'Wuerzel vum Heap ass
  • D'lénkst Kand vun ass
  • D'rietst Kand vun ass
  • Den iwwergeuerdnete Knuet vun ass (ofgerënnt)
  • Een Element ass ee Blat, wann gëllt. ( ass d'Unzuel vun den Elementer)

Funktiounsweis[änneren | Quelltext änneren]

Heapsort besteet aus zwou Phasen:

  • der Opbauphas, déi een Tableau 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-Eegenschaft 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-Eegenschaft verletzt. D'Iddi ass et elo, fir dëst Element erofwanderen ze loossen, bis d'Heap-Eegenschaft 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-Eegenschaft 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 (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-Eegenschaft 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: ) ze realiséieren ass. D'Zortéierung an der Selektiounsphas brauch am schlëmmste Fall (Worst Case) awer iwwerlineär Zäit (). Also kann Heapsort een Tableau vun der Gréisst am schlëmmste Fall an Zäit zortéieren.

Den allgemengen Zortéierproblem huet eng Komplexitéit vun , 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