Wikibooks

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
Abgerufen von „https://de.wikibooks.org/w/index.php?title=Algorithmensammlung:_Sortierverfahren:_Heapsort&oldid=1019820“