31.3.2 Implementierung |
|
Von der Liste zum binären Baum |
Auch den Heapsortalgorithmus 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 Wir wollen jetzt den Algorithmus
implementieren. |
|
|
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 rneut 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 n ur von der zur gleichen Klasse gehörenden Methode heapSort(int[] liste] aufgerufen wird, privat. |
|
private static void macheHeap(int[]
liste) { |
|
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 mit der Wurzel
i
heap macht. Die Methode, die das leistet ist
macheHeapFuerKnoten(liste,
i, liste.length-1 )
der man die Liste, den Knoten, ab dem heap gemacht werden soll und die
Listenlänge übergibt. 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,
|
|
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. |
|
|
|
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. Ersetzen Sie in der Klasse Sortieren alle Vertauschungsroutinen durch den Aufruf der Methode tausche(...). Die Lösung findet sich in der Datei Sortieren.java im Download. |
Fussnote | |
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 erionnern, 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 | 31.3.3 Übungen |
zur Startseite | www.pohlig.de (C) MPohlig 2004 |