29.4.2 Die Implementierung des Heapsort-Algorithmus
 
Von der Liste zum binären Baum Auch den Heapsort-Algorithmus wollen wir, wie schon bei den bereits vorgestellten Sortieralgorithmen, auf Listen, genauer Reihungen von int-Zahlen anwenden. Der binäre Baum, den wir heap machen, dient uns dazu nur als Modell. Wenn wir in diesem Abschnitt also von einem Binärbaum sprechen, so meinen wir eigentlich einen Modell-Binärbaum. Was das heißt, wird gleich deutlicher:

Zunächst müssen wir die Liste der int-Zahlen, die wir sortieren wollen, in die Knoten eines Binärbaums einlesen. Wir machen dazu ein konkretes Beispiel und geben uns eine 11-elementige Liste vor: [7, 12, 0, 5, 9, 1, 3, 8, 13, 10, 15] und denken uns dazu einen binären Baum mit 11 Knoten (Modell). Die Konten werden "zeilenweise von links nach rechts" aufgefüllt. Das erste Bild zeigt dazu den leeren Baum, dessen Knoten dann die Werte der Liste aufnehmen können. Die Zahlen neben den Kreisen stellen die Platznummern der Knoten dar. Die Platznummern sind dabei so vergeben, dass ihr Wert die Reihenfolge markiert, in der die Knoten mit Werte belegt werden.

Im nächsten Schritt werden die Werte aus der Liste in den Baum eingetragen:

Wenn i die "Nummer" eines Kotens ist, so lässt sich über die Ganzzahldivison i/2 die Knotennummer seines Vater bestimmen. So ist der Vater des Knotens
K-4 der Knoten mit der Nummer 4/2 = 2. Ebenso ist Knoten K-2 auch Vater von Knoten 5, denn die Ganzzahldivision 5/2 liefert ebenfalls 2. Umkehrt lässt sich auch zu einem Knoten, wenn er nicht Wurzel eines leeren Teilbaums ist der Sohn bzw. die zwei Söhne berechnen. Denn, ist i die Nummer eines Knotens, so ist 2*i, falls 2*i die Länge der Liste noch nicht überschritten hat, die Knotennummer des "linken Sohns", und entsprechend ist 2*i+1 die Knoten-nummer des "rechten Sohns", wenn 2*i+1 nicht die Listenlänge überschritten hat. Wir sehen also, eine Liste lässt sich leicht in einen binären Baum transformieren: a[i] der Wert der i-ten Stelle in der Liste wird somit zum Wert des i-ten Knotens, wenn der binäre Baum wie oben beschrieben erzeugt wurde.

Wir wollen jetzt den Algorithmus implementieren.
 

 
public static void heapSort(int[] liste) {

  macheHeap(liste);

  for (int i = liste.length-1; i > 0; i--) {

    tausche(liste, 0, i);

    macheHeapFuerKnoten(liste, 0, i-1);

  }

}
  Die öffentliche Methode macht die übergebene Liste zunächst heap. Das kleinste Element befindet sich an der Stelle der Wurzel. Also wird der Wert des letzten Elements, mit dem Wert des Elements mit der höchsten Platznummer, nämlich liste.length-1 vertauscht. Der letzte Listeneintrag gehört schon zur sortierten Teilliste. Danach muss das Feld,  jetzt ohne den letzten Feldeintrag erneut heap gemacht werden. Dies geschieht mit dem Aufruf der Methode macheHeapFierKnoten(liste, 0, i-1). Der letzte Wert in der Parameterliste ist der bei jedem Schleifendurchgang kürzer werdenden zu sortierende Feld. Diese erneut heap gemachte, um 1 kürzere Restliste ist wieder das kleinste Element in der Wurzel angelegt, deren Inhalt jetzt mit dem vorletzten Feldeintrag vertauscht wird. Dieser Vorgang wiederholt sich zum letzten Mal, wenn die übrig gebliebene Restliste nur noch zwei Einträge hat.

Kommen wir zu der Methode, die die Liste zum ersten Mal heap macht. Sie ist, das sie nur von der zur gleichen Klasse gehörenden Methode
heapSort(int[] liste] aufgerufen wird, privat.
 
  private static void macheHeap(int[] liste) {
  for (int i = (liste.length/2); i >= 0; i--) {
    macheHeapFuerKnoten(liste, i, liste.length-1);
  }
}
  Da alle Blätter des Baumes schon heap sind, muss man bei dem am meisten 'rechts' gelegenen Knotens in der vorletzten Zeile des Modellbaumes mit dem heap-Machen beginnen. Dies erreicht man, wenn man das heap-Machen an der Stelle i = liste.length/2 beginnt. Man macht aber einen Teilbaum heap, wenn man ihn mit der Wurzel i heap macht. Die Methode, die das leistet ist macheHeapFuerKnoten(liste, i, liste.length-1). Der Methode übergibt  man die Liste, den Knoten, ab dem heap gemacht werden soll und die Listenlänge. Man beachte, dass beim Aufruf dieser Methode die ganze Liste heap gemacht werden soll und deshalb auch die Länge der ganzen Liste übergeben wird.1) Warum man den letzteren Wert übergibt, wo er doch mit der Liste implizit mit übergeben wird, sehen wir erst, wenn wir uns den Quellkode dieser Methode uns genauer ansehen.
 
  private static void macheHeapFuerKnoten(int[] liste,
                                        int
dieserKnoten,
                                        int
heapGroesse) {
  int linkerSohn = 2 * dieserKnoten + 1;
  int rechterSohn = linkerSohn + 1;
  int sohn;
  if (linkerSohn <= heapGroesse &&              
#1
      rechterSohn > heapGroesse) {
      //nur ein Sohn (links)
   
if (liste[linkerSohn] < liste[dieserKnoten])
#2
             tausche(liste, linkerSohn, dieserKnoten);

  }
  else
{                                        
#3
    if (rechterSohn <= heapGroesse) {
      sohn = liste[linkerSohn] < liste[rechterSohn] ?
             linkerSohn :
             rechterSohn;
      if (liste[sohn] < liste[dieserKnoten]) {  
#4
        tausche(liste, dieserKnoten, sohn);
        macheHeapFuerKnoten(liste, sohn, heapGroesse);
      }
    }
  }
}
 
  Zuerst werden rechter und linker Sohn des übergebenen 'Knotens' berechnet. Die Bedingung im ersten if-Zweig (#1) ist nur dann erfüllt, wenn der Knoten nur einen linken Sohn besitzt. Der Vergleich des Wertes des Sohnes mit dem Wert seines Vaters entscheidet ob getauscht werden soll(#2).  Es gibt in diesem Fall keinen Teilbaum mehr unter dem 'Knoten' der wieder heap gemacht werden muss. Falls der übergebene 'Knoten' zwei Söhne hat (#3), werden die Werte der beiden Söhne verglichen und der Sohn mit dem kleineren Wert in der Variablen in sohn gespeichert. Der Vergleich des Wertes von sohn mit dem des Vaters entscheidet wieder über das Vertauschen der Werte (#4). Da durch das Vertauschen der Teilbaum unter dem 'Knoten' die Eigenschaft heap zu sein möglicherweise verloren hat, muss die Methode macheHeapFuer(..) für sohn aufgerufen werden.

Bleibt noch die Methode
tausche(int[] liste, int x, int y), die wir wegen ihrer Einfachheit nicht zu kommentieren brauchen.
 
 
private static void tausche(int[] liste, int x, int y) {

  int tmp = liste[x];

  liste[x] = liste[y];

  liste[y] = tmp;

}

Download:
Sortieren.java
SortierenDemo. java
So wie wir den Heapsort-Algorithmus implementiert haben, wird die Liste fallend sortiert. Was muss man alles verändern, um ein steigend sortierte Liste zu bekommen? Machen Sie die Veränderung als Übung.
   
Fussnote  

1)

Würde man die Methode macheHeapFuerKnoten(..) nur hier benutzen, würde man auf den letzten Parameter verzichten, da die Listenlänge implizit mit der Übergabe der Liste selbt mitübergebn wird. Aber, wir erinnern, dieselbe Methode wird auch in heapSort(..) benötigt, dort aber für Teillisten, deren Länge bei jedem Schleifendurchgang dekrementiert wird, wobei die Länge der Liste liste unverändert bleibt. [zurück]
   
zu 28.4.3 Übungen
zur Startseite www.pohlig.de  (C) MPohlig 2006