Algorithmensammlung: Sortierverfahren: Heapsort
Algorithmensammlung: Sortierverfahren
Heapsort
[Bearbeiten]Heapsort ist ein Sortieralgorithmus, der die Datenstruktur der Halde ausnutzt, um in-place zu sortieren. Der Algorithmus ist dabei auch im Worst-Case in der Komplexitätsklasse und damit in diesem Fall schneller als Quicksort.
Für weitere Informationen siehe Heapsort.
To-Do:
Quelltexte ins Deutsche übersetzen
To-Do:
Quelltexte überprüfen ! Bei mir wird mit den Testdaten 47,100,101,1023,1023,102,800,888,11,777,42,6,0,0,56,1000,900,810,61,77,87,34,45,501,504,986,15,115,1,78,403,19 sowohl in C# als auch in Pascal 47 zur größten Zahl.
C++
[Bearbeiten]#include <iterator>
template< typename Iterator >
void adjust_heap( Iterator first
, typename std::iterator_traits< Iterator >::difference_type current
, typename std::iterator_traits< Iterator >::difference_type size
, typename std::iterator_traits< Iterator >::value_type tmp )
{
typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
diff_t top = current, next = 2 * current + 2;
for ( ; next < size; current = next, next = 2 * next + 2 )
{
if ( *(first + next) < *(first + next - 1) )
--next;
*(first + current) = *(first + next);
}
if ( next == size )
*(first + current) = *(first + size - 1), current = size - 1;
for ( next = (current - 1) / 2;
top < current && *(first + next) < tmp;
current = next, next = (current - 1) / 2 )
{
*(first + current) = *(first + next);
}
*(first + current) = tmp;
}
template< typename Iterator >
void pop_heap( Iterator first, Iterator last)
{
typedef typename std::iterator_traits< Iterator >::value_type value_t;
value_t tmp = *--last;
*last = *first;
adjust_heap( first, 0, last - first, tmp );
}
template< typename Iterator >
void heap_sort( Iterator first, Iterator last )
{
typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
for ( diff_t current = (last - first) / 2 - 1; current >= 0; --current )
adjust_heap( first, current, last - first, *(first + current) );
while ( first < last )
pop_heap( first, last-- );
}
C#
[Bearbeiten] //Die Implementierung wurde der JAVA-Version nachempfunden
/// <summary>
/// sortiert ein Array mit heapsort
/// </summary>
/// <param name="a">Das Array</param>
/// <remarks></remarks>
private void heapSort(ref int[] a)
{
generateMaxHeap(a);
//hier wird sortiert
for (int i = a.Length - 1; i > 0; i += -1) {
vertausche(a, i, 0);
versenke(a, 0, i);
}
}
/// <summary>
/// Erstellt einen MaxHeap Baum im Array
/// </summary>
/// <param name="a">das array</param>
/// <remarks></remarks>
private void generateMaxHeap(int[] a)
{
//starte von der Mitte rückwärts.
for (int i = (int)(a.Length / 2 - 1); i >= 0; i += -1) {
versenke(a, i, a.Length);
}
}
/// <summary>
/// versenkt ein element im baum
/// </summary>
/// <param name="a">Das Array</param>
/// <param name="i">Das zu versenkende Element</param>
/// <param name="n">Die letzte Stelle im Baum die beachtet werden soll</param>
/// <remarks></remarks>
private void versenke(int[] a, int i, int n)
{
while (i <= (n / 2 - 1)) {
int kindIndex = (i + 1) * 2 - 1;
//berechnet den Index des linken kind
//bestimme ob ein rechtes Kind existiert
if (kindIndex + 1 <= n - 1) {
//rechtes kind existiert
if (a[kindIndex] < a[kindIndex + 1])
kindIndex += 1;
//wenn rechtes kind größer ist nimm das
}
//teste ob element sinken muss
if (a[i] < a[kindIndex]) {
vertausche(a, i, kindIndex);
i = kindIndex;
} else { break; }
}
}
/// <summary>
/// Vertauscht die arraypositionen von i und kindIndex
/// </summary>
/// <param name="a">a Das Array in dem getauscht wird</param>
/// <param name="i">i der erste index</param>
/// <param name="kindIndex">kindIndex der 2. index</param>
/// <remarks></remarks>
private void vertausche(int[] a, int i, int kindIndex)
{
int z = a[i];
a[i] = a[kindIndex];
a[kindIndex] = z;
}
Fortran
[Bearbeiten] # Die Implementierung wurde der JAVA-Version nachempfunden
subroutine vertausche (a, size, x, y)
integer x, y, z, size
integer a(size)
z = a(x)
a(x) = a(y)
a(y) = z
return
end
subroutine versickere (a, size, i)
integer i, size, ln, j
integer a(size)
j = i
do while (j.LE.(size/2))
ln = 2*j
if (ln.LT.size) then
if ((a(ln+1)).GT.(a(ln))) ln = ln+1
end if
if ((a(ln)).GT.(a(j))) then
call vertausche(a,Size,j,ln)
j = ln
else
j = size
end if
end do
return
end
subroutine ueberfuehreInHeap (a, size)
integer size, i
integer a(size)
do i = size /2 , 1 , -1
call versickere (a, size, i)
end do
return
end
subroutine heapSort (a, size)
integer size
integer a(size)
call ueberfuehreInHeap(a,size)
do i=size, 1, -1
call vertausche(a, size, 1, i)
call versickere(a, i-1, 1)
end do
return
end
Java
[Bearbeiten]/**
* sortiert ein Array mit heapsort
* @param a das array
*/
private static void heapSort(int[] a) {
generateMaxHeap(a);
//hier wird sortiert
for(int i = a.length -1; i > 0; i--) {
vertausche(a, i, 0);
versenke(a, 0, i);
}
}
/**
* Erstellt einen MaxHeap Baum im Array
* @param a das array
*/
private static void generateMaxHeap(int[] a) {
//starte von der Mitte rückwärts.
for(int i = (a.length / 2) - 1; i >= 0 ; i--) {
versenke(a, i, a.length);
}
}
/**
* versenkt ein element im baum
* @param a Das Array
* @param i Das zu versenkende Element
* @param n Die letzte Stelle im Baum die beachtet werden soll
*/
private static void versenke(int[] a, int i, int n) {
while(i <= (n / 2) - 1) {
int kindIndex = ((i+1) * 2) - 1; // berechnet den Index des linken kind
//bestimme ob ein rechtes Kind existiert
if(kindIndex + 1 <= n -1) {
//rechtes kind existiert
if(a[kindIndex] < a[kindIndex+1]) {
kindIndex++; // wenn rechtes kind größer ist nimm das
}
}
//teste ob element sinken muss
if(a[i] < a[kindIndex]) {
vertausche(a,i,kindIndex); //element versenken
i = kindIndex; // wiederhole den vorgang mit der neuen position
} else break;
}
}
/**
* Vertauscht die arraypositionen von i und kindIndex
* @param a Das Array in dem getauscht wird
* @param i der erste index
* @param kindIndex der 2. index
*/
private static void vertausche(int[] a, int i, int kindIndex) {
int z = a[i];
a[i] = a[kindIndex];
a[kindIndex] = z;
}
Pascal
[Bearbeiten]const SIZE = 20000;
type TFeld = array[1..SIZE] of integer;
procedure heapsort(var f:TFeld);
procedure genheap(var f:TFeld); { Heap (mit linearem Aufwand) aufbauen }
var i,j,max,temp:integer;
begin
for i := SIZE div 2 downto 1 do begin { zweite Hälfte des Feldes braucht nicht betrachtet werden }
j:=i;
while j <= SIZE div 2 do begin
max := j * 2 + 1; { finde Maximum der (beiden) Söhne }
if max > SIZE then dec(max)
else if f[max-1] > f[max] then dec(max);
if f[j] < f[max] then begin { ggf. tauschen }
temp := f[j];
f[j] := f[max];
f[max] := temp;
end;
j := max;
end;
end;
end;
function popmax(var f:TFeld;heapsize:integer):integer;
var i,max,temp:integer;
begin
popmax := f[1];
f[1] := f[heapsize];
i := 1;
while i <= (heapsize div 2) do begin { letztes Element an Anfang setzen und versickern lassen }
max := i * 2 + 1; { finde Maximum der (beiden) Söhne }
if max > heapsize then dec(max)
else if f[max-1] > f[max] then dec(max);
if f[i] < f[max] then begin { ggf. tauschen }
temp := f[i];
f[i] := f[max];
f[max] := temp;
end;
i := max;
end;
end;
var i:integer;
begin
genheap(f);
for i:=SIZE downto 1 do f[i] := popmax(f,i);
end;
Python 2
[Bearbeiten]from math import *
import random
class tree:
# initialize tree
def __init__(self,list):
self.list = list
# Exchange-Operation
def exch(self, i,j):
self.list[i], self.list[j] = self.list[j], self.list[i]
# sink item
# die iterative Variante frei nach Robert Sedgewick
def sink(self,index):
N = len(self.list)
k = index+1
while 2*k <= N:
j=2*k
if j<N and self.list[j-1] < self.list[j]:
j += 1
if self.list[k-1] >= self.list[j-1]:
break
self.exch(k-1,j-1)
k = j
def getHighest(self):
a = self.list[0]
self.exch(0,-1)
del self.list[-1]
self.sink(0)
return a
# Generating random numbers
a = [random.randint(1,10000) for i in range(100)]
a = tree(a)
print a.list
# Build Heap
for i in range(len(a.list)-1, -1, -1):
a.sink(i)
# UnBuild Heap to view as sorted list
out = [a.getHighest() for i in range(len(a.list))]
out.reverse()
print out
Visual Basic .NET
[Bearbeiten] 'Die Implementierung wurde der JAVA-Version nachempfunden
''' <summary>
''' sortiert ein Array mit heapsort
''' </summary>
''' <param name="a">Das Array</param>
''' <remarks></remarks>
Private Sub heapSort(ByRef a As Integer())
generateMaxHeap(a)
'hier wird sortiert
For i As Integer = a.Length - 1 To 0 Step -1
vertausche(a, i, 0)
versenke(a, 0, i)
Next
End Sub
''' <summary>
''' Erstellt einen MaxHeap Baum im Array
''' </summary>
''' <param name="a">das array</param>
''' <remarks></remarks>
Private Sub generateMaxHeap(ByVal a As Integer())
'starte von der Mitte rückwärts.
For i As Integer = CInt(a.Length / 2 - 1) To 1 Step -1
versenke(a, i, a.Length)
Next
End Sub
''' <summary>
''' versenkt ein element im baum
''' </summary>
''' <param name="a">Das Array</param>
''' <param name="i">Das zu versenkende Element</param>
''' <param name="n">Die letzte Stelle im Baum die beachtet werden soll</param>
''' <remarks></remarks>
Private Sub versenke(ByRef a As Integer(), ByVal i As Integer, ByVal n As Integer)
While i <= (n / 2 - 1)
Dim kindIndex As Integer = (i + 1) * 2 - 1 'berechnet den Index des linken kind
'bestimme ob ein rechtes Kind existiert
If kindIndex + 1 <= n - 1 Then
'rechtes kind existiert
If a(kindIndex) < a(kindIndex + 1) Then kindIndex += 1 'wenn rechtes kind größer ist nimm das
End If
'teste ob element sinken muss
If a(i) < a(kindIndex) Then
vertausche(a, i, kindIndex)
i = kindIndex
Else : Exit While
End If
End While
End Sub
''' <summary>
''' Vertauscht die arraypositionen von i und kindIndex
''' </summary>
''' <param name="a">a Das Array in dem getauscht wird</param>
''' <param name="i">i der erste index</param>
''' <param name="kindIndex">kindIndex der 2. index</param>
''' <remarks></remarks>
Private Sub vertausche(ByRef a As Integer(), ByVal i As Integer, ByVal kindIndex As Integer)
Dim z As Integer = a(i)
a(i) = a(kindIndex)
a(kindIndex) = z
End Sub