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

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 $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 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 $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 Eegenschaft 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

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-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 $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

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: $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)$, 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

Commons: Heap sort – Biller, Videoen oder Audiodateien