Einführung in Heap Sort In Java

Heapsort in Java ist eine vergleichsbasierte Sortiertechnik, bei der die Datenstruktur Binary Heap verwendet wird. Diese Sortierung ist fast dieselbe wie bei der 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, welche binäre Heap-Sortierung in Java vorliegt.

  • Baumbasierte Datenstruktur.
  • Beende den Binary Tree.
  • Es kann bis zu zwei Kinder haben.
  • Der Wert im Stammknoten kann größer (maximaler Heap) oder kleiner (minimaler Heap) sein.

Wie funktioniert die Heap-Sortierung in Java?

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

Heapify

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 Knoten des Heaps anzupassen. Wenn Sie max heap erstellen möchten, wird das aktuelle Element mit seinen untergeordneten Elementen verglichen. Wenn der Wert der untergeordneten Elemente größer als das aktuelle Element ist, wird der Austausch mit dem größten Element in einem linken oder rechten untergeordneten Element durchgeführt. In ähnlicher Weise wird, wenn ein Min-Heap erstellt werden muss, der Austausch mit dem kleinsten Element im linken oder rechten untergeordneten Element durchgeführt. Zum Beispiel ist das folgende unser Eingabearray,

Wir können dies als einen Baum anstelle eines Arrays betrachten. Das erste Element ist root, das zweite ist das linke untergeordnete Element von root, das dritte Element ist das rechte untergeordnete Element von root und so weiter.

Um den Haufen in einen Baum zu verwandeln, durchqueren Sie den Baum von unten nach oben. Da die Blattknoten keine Kinder haben, schauen wir uns die nächste Ebene an. dh ist 5 und 7.

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

Gehen wir zum nächsten Element 7 über, in dem 8 und 2 die Kinder sind. Ähnlich wie bei den Elementen 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 root größer ist. Das Vertauschen von 3 und 9 wird durchgeführt, um die Wurzel größer zu machen. Wiederholen Sie den Vorgang, bis sich ein gültiger Heap gebildet hat (siehe unten).

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. Heapify den Baum
  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. Heapify den Baum
  4. Wiederholen Sie den Vorgang, bis das Array sortiert ist

Versuchen wir nun, den oben erhaltenen Heap in aufsteigender Reihenfolge nach dem angegebenen Algorithmus zu sortieren. Entfernen Sie zunächst das größte Element. dh root und ersetze es durch das letzte Element.

Heapifizieren Sie nun den gebildeten Baum und fügen Sie das entfernte Element wie unten gezeigt in das letzte Array ein

Entfernen Sie erneut das Stammelement, ersetzen Sie es durch das letzte Element und heapifizieren Sie es.

Setzen Sie das entfernte Element in die freie 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.

Heapifizieren Sie den Baum wie unten gezeigt.

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

Den Baum häufen.

Element ausbauen 4.

Schon wieder hoffnungsvoll.

Zuletzt wird ein sortiertes Array wie dieses gebildet.

Beispiele zur Implementierung von Heap Sort in Java

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 heapify until a heap is formed
heapify(array, i, 0);
)
)
// Heapify 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 array(largestelement))
largestelement = leftChild ;
//right child is greater than largest
if (rightChild array(largestelement))
largestelement = rightChild ;
// If largestelement 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. out .println("Input array is: " + Arrays. toString (array));
HeapSort obj = new HeapSort();
obj.sort(array);
System. out .println("Sorted array is : " + Arrays. toString (array));
)
)

Ausgabe

Fazit

Heap-Sortierung ist eine Sortiertechnik, die von der Struktur der binären Heap-Daten abhängt. Es ähnelt fast der Auswahlsortierung und verwendet keine separaten Arrays zum Sortieren und Speichern.

Empfohlener Artikel

Dies war ein Leitfaden für die Heap-Sortierung in Java. Hier diskutieren wir die Arbeitsweise, den Sortieralgorithmus mit aufsteigender und absteigender Reihenfolge und Beispiele mit Beispielcode. Sie können auch unsere anderen Artikelvorschläge durchgehen, um mehr zu erfahren -

  1. JavaScript-Mathematikfunktionen
  2. Layout in Java
  3. Java-Compiler
  4. Anleitung zum Zusammenführen von Sort in Java
  5. Anleitung zum Sortieren von Haufen in C
  6. Beispiele für die Heap-Sortierung in C ++

Kategorie:

Software-Entwicklung