Heapsort

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
framed|Een Heap an deen entspriechenden Tableau dozou
Een Heap ass eng Bamstruktur, där hir Kniet mat Schlësselen (Zuelen) markéiert sinn, soudatt 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 entweeder 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
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
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
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
De follgende 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
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 , soudatt dës Lafzäit déi bescht ass, déi ee mat engem allgemengen Zortéierverfahren erreeche kann.

 Literatur 
 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 

Kategorie:Algorithmen

no:Sorteringsalgoritme#Heap sort