Heap-Sortierung in Java

Heapsort in Java ist eine vergleichsbasierte Sortiertechnik, bei der die Datenstruktur Binary Heap verwendet wird. Diese Sortierung ist fast die gleiche wie die Auswahlsortierung, bei der das größte Element ausgewählt und am Ende platziert wird und der Vorgang für alle Elemente wiederholt wird. Um die Heap-Sortierung zu verstehen, sehen wir uns an, was die binäre Heap-Sortierung in Java ist.

• Baumbasierte Datenstruktur.
• Vollständiger Binärbaum.
• Es kann bis zu zwei Kinder haben.
• Der Wert im Wurzelknoten kann größer (Max. Heap) oder kleiner (Min. Heap) sein

Wie funktioniert Heap Sort in Java?

Bevor wir zum Algorithmus übergehen, wollen wir sehen, was Heapify ist.

WERBUNG Beliebter Kurs in dieser Kategorie JAVA MASTERY - Spezialisierung | 78 Kursreihe | 15 Probetests

Haufen

Nachdem ein Heap mit den Eingabedaten erstellt wurde, ist die Heap-Eigenschaft möglicherweise nicht erfüllt. Um dies zu erreichen, wird eine Funktion namens heapify verwendet, um die Heap-Knoten anzupassen. Wenn wir einen maximalen Heap erstellen möchten, wird das aktuelle Element mit seinen untergeordneten Elementen verglichen. Wenn der Wert der untergeordneten Elemente größer als der des aktuellen Elements ist, erfolgt der Austausch mit dem größten Element in einem linken oder rechten untergeordneten Element. Wenn ein Min-Heap erstellt werden muss, erfolgt der Austausch ebenfalls mit dem kleinsten Element im linken oder rechten untergeordneten Element. Das Folgende ist beispielsweise unser Eingabearray:

Wir können dies als Baum statt als Array betrachten. Das erste Element wird die Wurzel sein; das zweite wird das linke Kind der Wurzel sein; das dritte Element ist das rechte Kind der Wurzel und so weiter.

Um den Haufen in einen Baum umzuwandeln, durchqueren Sie den Baum von unten nach oben. Da die Blattknoten keine untergeordneten Knoten haben, schauen wir uns die nächste Ebene an. d.h. ist 5 und 7.

Wir können bei 5 beginnen, da es auf der linken Seite ist. Hier hat 5 zwei Kinder: 9 und 4, wobei 9 größer als der Elternknoten 5 ist. Um die Eltern größer zu machen, tauschen wir 5 und 9. Nach dem Tauschen sieht der Baum wie unten gezeigt aus.

Lassen Sie uns zum nächsten Element übergehen, 7, wobei 8 und 2 die Kinder sind. Ähnlich wie die Elemente 9 und 4 werden 7 und 8 wie im folgenden Baum vertauscht.

Schließlich hat 3 zwei Kinder – 9 und 8, wobei 9 unter den Kindern und der Wurzel größer ist. Daher werden 3 und 9 vertauscht, um die Wurzel größer zu machen. Wiederholen Sie den Vorgang, bis ein gültiger Heap gebildet ist, wie unten gezeigt.

Algorithmus für die Heap-Sortierung in aufsteigender Reihenfolge

1. Erstellen Sie einen Max Heap mit den Eingabedaten
2. Ersetzen Sie das letzte Element durch das größte Element im Heap
3. Haufen Sie den Baum auf
4. Wiederholen Sie den Vorgang, bis das Array sortiert ist

Algorithmus für die Heap-Sortierung in absteigender Reihenfolge

1. Erstellen Sie einen Min Heap mit den Eingabedaten
2. Ersetzen Sie das letzte Element durch das kleinste Element im Heap
3. Haufen Sie den Baum auf
4. Wiederholen Sie den Vorgang, bis das Array sortiert ist

Nun versuchen wir, den oben erhaltenen Heap mithilfe des angegebenen Algorithmus in aufsteigender Reihenfolge zu sortieren. Entfernen Sie zunächst das größte Element. d.h. rooten und durch das letzte Element ersetzen.

Heapifizieren Sie nun den gebildeten Baum und fügen Sie das entfernte Element am Ende des Arrays ein, wie unten gezeigt.

Entfernen Sie erneut das Wurzelelement, ersetzen Sie es durch das letzte Element und häufen Sie es.

Fügen Sie das entfernte Element an der freien Position ein. Jetzt können Sie sehen, dass das Ende des Arrays sortiert wird.

Entfernen Sie nun Element 7 und ersetzen Sie es durch 2.

Häufen Sie den Baum auf, wie unten gezeigt.

Wiederholen Sie den Vorgang, bis das Array sortiert ist. Element 5 entfernen.

Den Baum aufhäufen.

Element 4 entfernen.

Schon wieder gewaltig. 

Zuletzt wird ein sortiertes Array wie dieses gebildet.

Beispiele

Sehen wir uns nun den Quellcode von Heap Sort in Java an

//Java program to sort the elements using Heap sort
import java.util.Arrays;
public class HeapSort {
public void sort(int array[]) {
int size = array.length; //Assigning the length of array in a variable
// Create heap
for (int i = size / 2 - 1; i >= 0; i--)
heapify(array, size, i);
//Find the maximum element and replace it with the last element in the array
for (int i=size-1; i>=0; i--) {
int x = array[0];//largest element(It is available in the root)
array[0] = array[i];
array[i] = x;
// Recursively call <u>heapify</u> until a heap is formed
heapify(array, i, 0);
}
}
// <u>Heapify</u> function
void heapify(int array[], int SizeofHeap, int i) {
int largestelement = i; // Set largest element as root
int leftChild  = 2*i + 1; // index of left child = 2*i + 1
int rightChild  = 2*i + 2; //index of right child  = 2*i + 2
// left child is greater than root
if (leftChild  < SizeofHeap && array[leftChild ] > array[largestelement])
largestelement = leftChild ;
//right child is greater than largest
if (rightChild  < SizeofHeap && array[rightChild ] > array[largestelement])
largestelement = rightChild ;
// If <u>largestelement</u> is not root
if (largestelement != i) {
int temp = array[i];
array[i] = array[largestelement];
array[largestelement] = temp;
// Recursive call to  heapify the sub-tree
heapify(array, SizeofHeap, largestelement);
}
}
public static void main(String args[]) {
int array[] = {3,5,7,9,4,8,2};
System.<em>out</em>.println("Input array is: " + Arrays.<em>toString</em>(array));
HeapSort obj = new HeapSort();
obj.sort(array);
System.<em>out</em>.println("Sorted array is : " + Arrays.<em>toString</em>(array));
}
}

Ausgabe

Fazit

Heap Sort ist eine Sortiertechnik, die von der binären Heap-Datenstruktur abhängt. Es ähnelt fast der Auswahlsortierung und verwendet keine separaten Arrays für Sortierung und Heap.

 Empfohlene Artikel

Dies war eine Anleitung zur Heap-Sortierung in Java. Hier besprechen wir die Funktionsweise, den Sortieralgorithmus mit aufsteigender und absteigender Reihenfolge und Beispiele mit Beispielcode. Sie können auch unsere anderen empfohlenen Artikel durchsehen, um mehr zu erfahren –

1. Sortierung in Java zusammenführen
2. Heap-Sortierung in C
3. Heap-Sortierung in C++
4. Auswahlsortierung in Datenstruktur

Das obige ist der detaillierte Inhalt vonHeap-Sortierung in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!