Algorithmensammlung: Sortierverfahren: Heapsort

Algorithmensammlung: Sortierverfahren

• Countingsort
• Combsort
• Quicksort
• Heapsort
• Selectionsort
• Mergesort

Heapsort

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 $\mathcal{O}(n \cdot \log(n))$ und damit in diesem Fall schneller als Quicksort.

Für weitere Informationen siehe Heapsort.

C++

#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-- );
}

Java

/**  
 * 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

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

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

Fortran

 # 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

Visual Basic .NET

    '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(ByVal 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(ByVal 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

C#

   //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 >= 1; 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;
}