heap sort c with examples
Eine Einführung in die Heap-Sortierung mit Beispielen.
Heapsort ist eine der effizientesten Sortiertechniken. Diese Technik erstellt einen Heap aus dem angegebenen unsortierten Array und verwendet den Heap dann erneut, um das Array zu sortieren.
Heapsort ist eine Sortiertechnik, die auf Vergleichen basiert und binären Heap verwendet.
=> Lesen Sie die Easy C ++ - Schulungsserie durch.
wie man eine jnlp-Datei ausführt
Was du lernen wirst:
- Was ist ein binärer Haufen?
- Allgemeiner Algorithmus
- Illustration
- C ++ Beispiel
- Java-Beispiel
- Fazit
- Literatur-Empfehlungen
Was ist ein binärer Haufen?
Ein binärer Heap wird unter Verwendung eines vollständigen binären Baums dargestellt. Ein vollständiger Binärbaum ist ein Binärbaum, in dem alle Knoten auf jeder Ebene bis auf die Blattknoten vollständig gefüllt sind und die Knoten so weit wie links sind.
Ein binärer Heap oder einfach ein Heap ist ein vollständiger binärer Baum, in dem die Elemente oder Knoten so gespeichert werden, dass der Stammknoten größer als seine beiden untergeordneten Knoten ist. Dies wird auch als Max Heap bezeichnet.
Die Elemente im binären Heap können auch als Min-Heap gespeichert werden, wobei der Wurzelknoten kleiner als seine zwei untergeordneten Knoten ist. Wir können einen Heap als Binärbaum oder Array darstellen.
Wenn ein Heap als Array dargestellt wird und der Index bei 0 beginnt, wird das Stammelement bei 0 gespeichert. Befindet sich ein übergeordneter Knoten an der Position I, befindet sich der linke untergeordnete Knoten im Allgemeinen an der Position (2 * I +) 1) und der rechte Knoten ist bei (2 * I +2).
Allgemeiner Algorithmus
Nachstehend ist der allgemeine Algorithmus für die Heap-Sortiertechnik angegeben.
- Erstellen Sie aus den angegebenen Daten einen maximalen Heap, sodass der Stamm das höchste Element des Heaps ist.
- Entfernen Sie die Wurzel, d. H. Das höchste Element, aus dem Heap und ersetzen oder tauschen Sie es durch das letzte Element des Heaps.
- Passen Sie dann den maximalen Heap an, um die Eigenschaften des maximalen Heaps (Heapify) nicht zu verletzen.
- Der obige Schritt reduziert die Heap-Größe um 1.
- Wiederholen Sie die obigen drei Schritte, bis die Heap-Größe auf 1 reduziert ist.
Wie im allgemeinen Algorithmus zum Sortieren des angegebenen Datensatzes in aufsteigender Reihenfolge gezeigt, erstellen wir zunächst einen maximalen Heap für die angegebenen Daten.
Nehmen wir ein Beispiel, um einen maximalen Heap mit dem folgenden Datensatz zu erstellen.
6, 10, 2, 4, 1
Wir können einen Baum für diesen Datensatz wie folgt erstellen.
In der obigen Baumdarstellung repräsentieren die Zahlen in den Klammern die jeweiligen Positionen im Array.
Um einen maximalen Heap der obigen Darstellung zu erstellen, müssen wir die Heap-Bedingung erfüllen, dass der übergeordnete Knoten größer als seine untergeordneten Knoten sein sollte. Mit anderen Worten, wir müssen den Baum 'heapifizieren', um ihn in max-heap zu konvertieren.
Nach der Heapifizierung des obigen Baums erhalten wir den Max-Heap wie unten gezeigt.
Wie oben gezeigt, haben wir diesen Max-Heap aus einem Array generiert.
Als nächstes präsentieren wir eine Illustration einer Heap-Sortierung. Nachdem wir die Konstruktion von Max-Heap gesehen haben, überspringen wir die detaillierten Schritte, um einen Max-Heap zu erstellen, und zeigen den Max-Heap bei jedem Schritt direkt an.
Illustration
Betrachten Sie das folgende Array von Elementen. Wir müssen dieses Array mit der Heap-Sortiertechnik sortieren.
Erstellen wir einen Max-Heap wie unten gezeigt für das zu sortierende Array.
Sobald der Heap erstellt ist, stellen wir ihn wie unten gezeigt in Array-Form dar.
Jetzt vergleichen wir die 1stKnoten (root) mit dem letzten Knoten und tauschen Sie sie dann aus. Wie oben gezeigt, tauschen wir also 17 und 3, so dass 17 an der letzten Position und 3 an der ersten Position ist.
Jetzt entfernen wir den Knoten 17 aus dem Heap und fügen ihn in das sortierte Array ein, wie im schattierten Teil unten gezeigt.
Jetzt erstellen wir wieder einen Heap für die Array-Elemente. Diesmal wird die Heap-Größe um 1 reduziert, da wir ein Element (17) aus dem Heap gelöscht haben.
Der Haufen der verbleibenden Elemente ist unten dargestellt.
Im nächsten Schritt werden wir die gleichen Schritte wiederholen.
Wir vergleichen und tauschen das Stammelement und das letzte Element im Heap aus.
Nach dem Austauschen löschen wir das Element 12 aus dem Heap und verschieben es in das sortierte Array.
wie man .dat Datei liest
Wir konstruieren erneut einen maximalen Heap für die verbleibenden Elemente, wie unten gezeigt.
Jetzt tauschen wir die Wurzel und das letzte Element, d. H. 9 und 3. Nach dem Tauschen wird Element 9 aus dem Heap gelöscht und in ein sortiertes Array eingefügt.
Zu diesem Zeitpunkt haben wir nur drei Elemente im Heap, wie unten gezeigt.
Wir tauschen 6 und 3 aus und löschen das Element 6 aus dem Heap und fügen es dem sortierten Array hinzu.
Jetzt konstruieren wir einen Haufen der verbleibenden Elemente und tauschen beide miteinander aus.
Nach dem Vertauschen von 4 und 3 löschen wir Element 4 aus dem Heap und fügen es dem sortierten Array hinzu. Jetzt haben wir nur noch einen Knoten im Heap, wie unten gezeigt .
Jetzt, da nur noch ein Knoten übrig ist, löschen wir ihn vom Heap und fügen ihn dem sortierten Array hinzu.
Somit ist das oben gezeigte das sortierte Array, das wir als Ergebnis der Heap-Sortierung erhalten haben.
In der obigen Abbildung haben wir das Array in aufsteigender Reihenfolge sortiert. Wenn wir das Array in absteigender Reihenfolge sortieren müssen, müssen wir die gleichen Schritte ausführen, jedoch mit dem Min-Heap.
Der Heapsort-Algorithmus ist identisch mit der Auswahlsortierung, bei der das kleinste Element ausgewählt und in ein sortiertes Array eingefügt wird. Die Heap-Sortierung ist jedoch in Bezug auf die Leistung schneller als die Auswahlsortierung. Wir können sagen, dass Heapsort eine verbesserte Version der Auswahlsortierung ist.
Als nächstes werden wir Heapsort in C ++ und Java implementieren.
Die wichtigste Funktion in beiden Implementierungen ist die Funktion 'Heapify'. Diese Funktion wird von der Haupt-Heapsort-Routine aufgerufen, um den Teilbaum neu zu ordnen, sobald ein Knoten gelöscht wird oder wenn Max-Heap erstellt wird.
Wenn wir den Baum korrekt gehäuft haben, können wir nur dann die richtigen Elemente an ihren richtigen Positionen finden und somit wird das Array korrekt sortiert.
C ++ Beispiel
Es folgt der C ++ - Code für die Heapsort-Implementierung.
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i Ausgabe:
Eingabearray
4 17 3 12 9 6
Sortiertes Array
3 4 6 9 12 17
Als nächstes werden wir den Heapsort in Java implementieren
Java-Beispiel
// Java program to implement Heap Sort class HeapSort { public void heap_sort(int arr()) { int n = arr.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i=n-1; i>=0; i--) { // Move current root to end int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // heapify the sub-tree void heapify(int arr(), int n, int root) { int largest = root; // Initialize largest as root int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { int swap = arr(root); arr(root) = arr(largest); arr(largest) = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } //print array contents - utility function static void displayArray(int arr()) { int n = arr.length; for (int i=0; i Ausgabe:
Eingabearray:
4 17 3 12 9 6
Sortiertes Array:
Öffnen einer XML-Datei in Excel
3 4 6 9 12 17
Fazit
Heapsort ist eine vergleichsbasierte Sortiertechnik unter Verwendung eines binären Heaps.
Dies kann als Verbesserung gegenüber der Auswahlsortierung bezeichnet werden, da beide Sortiertechniken mit einer ähnlichen Logik arbeiten, das größte oder kleinste Element im Array wiederholt zu finden und es dann in das sortierte Array zu platzieren.
Die Heap-Sortierung verwendet Max-Heap oder Min-Heap, um das Array zu sortieren. Der erste Schritt bei der Heap-Sortierung besteht darin, einen Min- oder Max-Heap aus den Array-Daten zu erstellen und dann das Stammelement rekursiv zu löschen und den Heap zu heapifizieren, bis nur noch ein Knoten im Heap vorhanden ist.
Heapsort ist ein effizienter Algorithmus und arbeitet schneller als die Auswahlsortierung. Es kann verwendet werden, um ein fast sortiertes Array zu sortieren oder k größte oder kleinste Elemente im Array zu finden.
Damit haben wir unser Thema zu Sortiertechniken in C ++ abgeschlossen. Ab unserem nächsten Tutorial beginnen wir nacheinander mit den Datenstrukturen.
=> Suchen Sie hier nach der gesamten C ++ - Schulungsserie.
Literatur-Empfehlungen
- MongoDB Sort () -Methode mit Beispielen
- Unix-Sortierbefehl mit Syntax, Optionen und Beispielen
- Sortierung in C ++ mit Beispielen zusammenführen
- Shell-Sortierung in C ++ mit Beispielen
- Einfügungssortierung in C ++ mit Beispielen
- Auswahl In C ++ mit Beispielen sortieren
- Blasensortierung in C ++ mit Beispielen
- Schnelle Sortierung in C ++ mit Beispielen