Heap ist eine wichtige Struktur in der Datenstruktur. Nach dem Verständnis des Konzepts und des Betriebs von "Heap" können Sie schnell die Sortierung des Haufens beherrschen.
Das Konzept der Haufen
Heap ist ein besonderer kompletter Binärbaum. Wenn die Werte aller Knoten eines vollständig binären Baums nicht kleiner sind als ihre Kinder, wird er als großer Wurzelhaufen (oder großer oberer Haufen) bezeichnet. Wenn die Werte aller Knoten nicht größer sind als ihre Kinder, wird sie als kleiner Wurzelhaufen (oder kleiner oberer Haufen) bezeichnet.
In einem Array (das Stammknoten in der Indexnummer 0 speichert) ist es einfach, die folgende Gleichung zu erhalten (diese beiden Gleichungen sind sehr wichtig):
1. Der Knoten mit Index ist I, und die Koordinaten des übergeordneten Knotens sind (i-1)/2;
2. Der Knoten mit Index ist I, die Koordinaten des linken untergeordneten Knotens 2*i+1 und der rechte untergeordnete Knoten 2*i+2.
Einrichtung und Wartung von Haufen
Der Haufen kann mehrere Vorgänge unterstützen, aber jetzt kümmern wir uns nur um zwei Probleme:
1. Wie kann man es als Haufen aufbauen?
2. Wie kann die Komposition nach dem Löschen des oberen Elements des Haufens die Komposition an einen neuen Haufen anpassen?
Schauen wir uns zuerst die zweite Frage an. Angenommen, wir haben bereits einen vorgefertigten großen Wurzelstapel. Jetzt löschen wir das Stammelement, aber wir bewegen die anderen Elemente nicht. Denken Sie darüber nach, was passiert ist: Das Wurzelelement ist leer, aber die anderen Elemente behalten immer noch die Eigenschaften des Haufens bei. Wir können das letzte Element (Codename a) in die Position des Stammelements verschieben. Wenn es sich nicht um einen Sonderfall handelt, werden die Eigenschaften des Haufens zerstört. Dies liegt jedoch nur daran, dass A kleiner als eines seiner Kinderelemente ist. So können wir a und dieses untergeordnete Element in die Position schalten. Wenn A größer ist als alle seine Kinderelemente, wird der Haufen angepasst. Ansonsten wiederholen Sie den obigen Vorgang, Element A "sinken" in der Baumstruktur fort, bis er angemessen ist, und das Array stellt die Eigenschaften des Haufens wieder her. Der obige Vorgang wird allgemein als "Screening" bezeichnet und die Richtung ist offensichtlich von oben nach unten.
Dies gilt beim Löschen eines Elements, ebenso wie ein neues Element. Der Unterschied besteht darin, dass wir das neue Element am Ende platzieren und es dann mit seinem übergeordneten Knoten vergleichen, dh es von unten nach oben filtern.
Wie kann man das erste Problem lösen?
Viele der Bücher zu Datenstrukturen, die ich gelesen habe, filtern vom ersten Nicht-Blattknoten ab, bis das Stammelement gefiltert ist. Diese Methode wird als "Filtermethode" bezeichnet, für die N/2 -Elemente der Schleifenfilterung erforderlich sind.
Wir können aber auch aus der Idee lernen, "etwas aus dem Nichts heraus zu erschaffen". Wir können das erste Element als Haufen betrachten und dann ständig neue Elemente hinzufügen. Diese Methode wird als "Einfügenmethode" bezeichnet, für die (n-1) Elemente die Schleifeneinfügung erforderlich sind.
Da die Filtermethode und die Insertionsmethode unterschiedlich sind, unterscheiden sich die Haufen, die sie erstellen, für dieselben Daten im Allgemeinen unterschiedlich.
Nach einem groben Verständnis des Haufens ist die Haufensortierung eine natürliche Sache.
Algorithmusübersicht/Ideen
Wir brauchen eine aufsteigende Sequenz. Was sollen wir tun? Wir können einen minimalen Haufen erstellen und dann jedes Mal das Stammelement ausgeben. Diese Methode erfordert jedoch zusätzlichen Platz (ansonsten verursacht sie eine Menge Elementbewegungen, und ihre Komplexität wird zu o (n^2)). Was ist, wenn wir eine Ortssortierung brauchen (d. H. Es ist keine o (n) Raumkomplexität zulässig)?
Es gibt einen Weg. Wir können den maximalen Haufen erstellen und dann den Maximalwert in der letzten Position und den zweiten Maximalwert in der letzten Position ausgeben ... da die maximale Elementausgabe jedes Mal den ersten Platz freigibt, können wir ein solches Element einfach platzieren, ohne zusätzlichen Speicherplatz zu benötigen. Sehr schöne Idee, oder?
öffentliche Klasse Heapsort {public static void main (String [] args) {int [] arr = {50, 10, 90, 30, 70, 40, 80, 60, 20}; System.out.println ("Bevor Sorting:"); für (int i = 0; i <arr.length; i ++) {System.out.print (arr [i]+""); } // Heap -Sortierung Heapsort (arr); System.out.println (); System.out.println ("After After Sorting:"); für (int i = 0; i <arr.length; i ++) {System.out.print (arr [i]+""); }} / *** HEAP-SORT* / private statische Hohlwahlen (int [] arr) {// Konstruieren Sie die zu sortierte Sequenz in einen großen oberen Heap für (int i = arr.length / 2; i> = 0; i-) {heapadjust (Arr, i, arr.Length); } // Tauschen Sie den Wurzelknoten jedes Maximalwerts nach und nach mit dem Endelement und passen Sie den binären Baum an, um ihn zu einem großen oberen Haufen für (int i = arr.Length-1; i> 0; i--) {Swap (arr, 0, i); // Tauschen Sie den Heap -Top -Datensatz mit dem letzten Datensatz des derzeit ungewöhnlichen Subsequence Heapadjust (arr, 0, i) aus; // Nach dem Austausch muss erneut überprüft werden, ob der Haufen den großen Top -Haufen trifft. Wenn es sich nicht erfüllt, muss es angepasst werden}} / *** Prozess des Erstellens des Heap* @param arr -Array, der sortiert werden muss* @param i Die Anzahl des Root -Knotens des Heaps, der gebaut werden muss* @param n der Länge des Array* / private statische Void -Haufen (int [] arr, int i, int i, int i, int n) {int n) {int n) {int n) {int n) {{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{int) “werden muss; int Vater; für (father = arr [i]; linkSchild (i) <n; i = child) {child = linkSchild (i); // Wenn der linke Unterbaum kleiner als der rechte Unterbaum ist, müssen Sie den rechten Subtree mit dem übergeordneten Knoten vergleichen, wenn (child! // Erhöhen Sie die Seriennummer um 1 und zeigen Sie auf den rechten Subtree} // Wenn der übergeordnete Knoten kleiner als der untergeordnete Knoten ist, müssen Sie sich austauschen, wenn (Vater <arr [child]) {arr [i] = arr [child]; } else {break; // Die große obere Heap -Struktur wird nicht zerstört, keine Anpassung ist erforderlich}} arr [i] = Vater; } // Holen Sie sich den linken untergeordneten Knoten private statische int links (int i) {return 2 * i + 1; } // Swap -Elementposition privater statischer void Swap (int [] arr, int index1, int index2) {int tmp = arr [index1]; arr [index1] = arr [index2]; arr [index2] = tmp; }}