Java Entwickler Experte
Heap sort – Heap-Sortierung in Java
Sortieralgorithmen werden verwendet, um die Elemente eines Arrays oder einer Liste in aufsteigender oder absteigender numerischer oder lexikografischer Reihenfolge neu zu ordnen. Die Sortierung ist sehr wichtig für die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten benötigen. Es gibt eine Reihe von verschiedenen Sortieralgorithmen. Die Auswahl eines geeigneten Algorithmus hängt von Faktoren wie der Größe und den Eigenschaften der Eingabedaten, dem verfügbaren Speicher und den Zeit- und Platzanforderungen ab. Um dir die Auswahl zu erleichtern, werden wir in unserer Serie die bekanntesten Datensortieralgorithmen nacheinander vorstellen, ihre Prinzipien, Vor- und Nachteile erklären und sie in Java programmieren. Bislang haben wir die folgenden Sortieralgorithmen behandelt:
In diesem Artikel erfährst du:
- Sortieralgorithmen – Einführung in das Sortieren von Daten,
- Bubble sort – Blasen-Sortierung,
- Comb sort – Kamm-Sortierung,
- Big O Notation –Komplexitätsanalyse von Algorithmen,
- Auswahlsortierung – Sortieren nach Auswahl,
- Einfügungssortierung – Sortieren nach Einfügung,
- Zählende Sortierung – Sortieren durch Zählen.
Heute werden wir uns das Sortieren mit Hilfe der Heap-Sort-Datenstruktur ansehen.
Haufen-Sortieren
Heapsort, der 1964 von J. W. J. Williams entwickelt wurde, ist ein recht populärer und sehr effizienter Sortieralgorithmus, der die Eingabedaten in einer Datenstruktur namens Heap speichert. Ein Heap ist ein vollständiger Binärbaum (complete binary tree). Er besitzt eine interessante Eigenschaft, die es ermöglicht, die Eltern- und Kindknoten jedes beliebigen Knotens im Baum leicht zu finden. Dies liegt daran, wie der Heap aus einem Eingabearray konstruiert wird. Wenn der Index eines beliebigen Elements im Array i ist, dann gilt: Der linke Kindknoten hat den Index 2 * i + 1 Der rechte Kindknoten hat den Index 2 * i + 2 Der Elternknoten eines Elements mit Index i wird durch den ganzzahligen Wert von (i – 1) / 2 bestimmt. Der Wurzelknoten des Baums hat den Index 0. Gerade durch diese Indexarithmetik lässt sich das Eingabearray in einen vollständigen Binärbaum (Heap) abbilden, ohne dass zusätzlicher Speicherplatz reserviert werden muss. Besondere Formen des Heaps sind der sogenannte Max-Heap und Min-Heap, die beide im Heapsort-Algorithmus verwendet werden. In einem Max-Heap gilt, dass der Wert jedes Elternknotens größer ist als der seiner direkten (eine Ebene tiefer) und indirekten (zwei oder mehr Ebenen tiefer) Nachkommen. In einem Min-Heap ist der Wert des Elternknotens kleiner als der seiner Nachkommen. Für die aufsteigende Sortierung der Elemente verwenden wir einen Max-Heap, wobei der maximale Wert des Baums im Wurzelknoten steht. Für die absteigende Sortierung nutzen wir einen Min-Heap, bei dem der kleinste Wert im Wurzelknoten liegt.
Heap-Sort Algorithmus – Funktionsprinzip
Im ersten Schritt erstellen wir einen Heap aus dem eingegebenen Feature-Vektor. Wir wandeln diesen in die Max-Heap-Form um und erstellen dafür eine heapify-Methode. Diese vergleicht rekursiv das übergeordnete Element und seine Kinder und tauscht die Werte aus, um sicherzustellen, dass das Element mit dem höchsten Wert an die Wurzel des Baums verschoben wird. Letzteres wird dann mit dem letzten Blatt des Baums ausgetauscht und dieses Blatt (mit dem höchsten Wert) wird beschnitten. Dieses Element wird als sortiert betrachtet und die Größe des Heaps wird um 1 reduziert. Durch den Austausch des Wurzelknotens hat der Heap seine Max-Heap-Form verloren und wir müssen den gesamten Vorgang wiederholen. Während wir nach und nach die aktuell höchsten Werte aus dem Baum entfernen, führen wir die Sortierung durch. Die Sortierung endet, wenn nur noch ein Element im Heap übrig ist, das das kleinste ist und an die Spitze des Arrays gehört.
Vorteile des Heap-Sortieralgorithmus
- Stabile Zeitkomplexität O(n log n) in allen Fällen,
- benötigt keinen zusätzlichen Speicher,
- die Leistung des Algorithmus nicht mit der Menge der Eingabedaten abnimmt.
Nachteile des Heap-Sort Algorithmus
- Ungeeignet für eine kleine Anzahl von Elementen, da sich der Overhead beim Erstellen und Verschieben von Elementen im Heap bemerkbar macht,
- ist nicht stabil,
- ist nicht anpassungsfähig.
Zeitbedarf für Heap-Sortierung
| Algorithmus | Methode | Zeitliche Komplexität | Speicher | Stabil | ||
| schlechteste | durchschnittlich | beste | ||||
| Heap sort | Auswahl | O(n log n) | O(n log n) | O(n log n) | O(1) | Nein |
Heap sort Animation, Visualisierung, gif
Die Visualisierung der Heap-Sortierung sieht folgendermaßen aus:
Quelle: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms
Eine Animation des Algorithmus findest du z.B. auf Toptal. Es gibt 8 Arten von Algorithmen, du kannst die Animation auch rückwärts abspielen. Auf dieser Seite kannst du die Schritte des Algorithmus durchlaufen, so dass du den Zeitverbrauch des Algorithmus überprüfen kannst.
Heap-Sort-Implementierung, Java-Code
Wir werden nun die Implementierung des Heap-Sortieralgorithmus in Java zeigen.
HeapSort.java
package sorting;
public class HeapSort {
public void sort(int data[])
{
// Don't sort if there are no elements
if(data.length == 0)
return;
// Build Max-Heap by rearranging array
for (int i = data.length / 2 - 1; i >= 0; i--) {
heapify(data, data.length, i);
}
// Extract max element from the heap one by one
for (int i = data.length - 1; i > 0; i--) {
int temp = data[0];
data[0] = data[i];
data[i] = temp;
System.out.print("max-heap root node extraction: " + data[i] + " -> ");
printArray(data);
System.out.println("");
// Heapify root node
heapify(data, i, 0);
}
}
// Heapify the subtree by the index i, where n is size of the heap
void heapify(int data[], int n, int i) {
System.out.print("heapify (" + n + ", " + i + ") on ");
printArray(data);
// Find max of (root, left child, right child)
int max = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && data[left] > data[max])
max = left;
if (right < n && data[right] > data[max])
max = right;
// Swap and continue heapifying if root is not max
if (max != i) {
int swap = data[i];
data[i] = data[max];
data[max] = swap;
System.out.println(" => exchange " + data[max] + " for " + data[i]);
heapify(data, n, max);
}
else {
System.out.println(" => no change");
}
}
// Function to print an array
public void printArray(int data[])
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
//System.out.println();
}
}
Main.java
import sorting.HeapSort;
public class Main {
public static void main(String[] args) {
int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
HeapSort heapSort = new HeapSort();
System.out.print("Input: ");
heapSort.printArray(dataToSort);
System.out.println("");
heapSort.sort(dataToSort);
System.out.print("Sorted: ");
heapSort.printArray(dataToSort);
}
}Die Ausgabe dieses Beispiels ist:
Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausführen kannst. Lade Java Heap Sort Code hier herunter.
Wenn du ein Java Programmierer bist und nach Arbeit suchst, schau dir unsere Mitareiterbenefits an und reagiere auf die neuesten Stellenangebote.
