Überblick
Die Heap -Sortierung ist eine Baumauswahlsortierung, die eine effektive Verbesserung der direkten Sortierung der Direktauswahl darstellt.
Der Haufen ist wie folgt definiert: eine Abfolge von N -Elementen (K1, K2, ..., kN), wenn und nur wenn er zufrieden ist:
Es wird zu dieser Zeit als Stapel bezeichnet. Wie aus der Definition des Haufens ersichtlich ist, muss das obere Element des Haufens (d. H. Das erste Element) das kleinste Element (kleiner oberer Haufen) oder der größte Element (großer oberer Haufen) sein.
Wenn ein Haufen in einem eindimensionalen Array gespeichert wird, entspricht der Haufen einem vollständig binären Baum, und die Werte aller Nicht-Blattknoten (Knoten mit Kindern) sind nicht größer als die Werte ihrer Kinder und die Werte des Wurzelknotens (oberes Element des Heaps) sind die kleinsten (oder schwersten).
(a) Große Top -Heap -Sequenz: (96, 83, 27, 38, 11, 09)
(b) Kleine Top -Heap -Sequenz: (12, 36, 24, 85, 47, 30, 53, 91)
Zunächst wird die Sortierung der Sortierung von N-Nummern als nacheinander gespeicherter binärer Baum (eindimensionaler Arrayspeicher-Binärbaum) angesehen. Passen Sie ihre Speicherreihenfolge an, um ihn zu einem Haufen zu machen, und geben Sie das obere Element des Haufens aus, um das kleinste (oder größte) Element der N-Elemente zu erhalten. Setzen Sie dann die verbleibenden N-1-Elemente nach Haufen, geben Sie das obere Element des Haufens aus und erhalten Sie das Element, das das zweite kleine (oder das zweite große) unter den N-Elementen ist. Und so weiter, bis Sie endlich eine bestellte Sequenz mit n Knoten erhalten. Nennen Sie diesen Prozess Haufen.
Schritte & Beispiele
Bei der Implementierung der Heap -Sortierung sind zwei Probleme zu lösen:
(1) wie man N -Zahlen aufbaut, die in Stapel sortiert werden sollen;
(2) Wie man die verbleibenden N-1-Elemente anpasst, um das obere Element des Haufens auszugeben, um es zu einem neuen Haufen zu machen.
Bauen Sie die Haufen Methode (kleiner oberer Haufen):
Der Prozess des Erstellens eines Haufens für die anfängliche Sequenz ist ein Prozess des wiederholten Screenings.
Ein vollständiger binärer Baum von N -Knoten, dann ist der letzte Knoten der Unterbaum des N/2. -Knotens.
Der Filter beginnt mit dem Subtree mit dem N/2. -Knoten als Wurzel (N/2 ist der letzte Knoten mit dem Subtree), so dass der Subtree zum Haufen wird.
Filtern Sie dann die Unterbaume mit jedem Knoten als Wurzel nach vorne, um sie bis zum Wurzelknoten zu einem Haufen zu machen.
Wie in der Abbildung gezeigt, ist die ungeordnete Sequenz des Anfangsprozesses des Erstellens eines Haufens: (49, 38, 65, 97, 76, 13, 27, 49)
(a) Unordentliche Sequenz, anfänglicher Binärbaum, 97 (8/2 = 4 Knoten) ist der übergeordnete Knoten des letzten Knotens (49).
(b) 97> = 49, ersetzen Sie die Position und filtern Sie dann den vorherigen Knoten 65 von N/2.
(c) 13 <= 27 und 65> = 13, ersetzen Sie die Positionen von 65 und 13 und dann 38 (beide größer als es, kein Betrieb ist erforderlich), Filter 49.
(d) 13 <= 38 und 49> = 13, ersetzen Sie die Positionen von 49 und 13, 49> = 27 und ersetzen Sie die Positionen von 49 und 27.
(e) Endlich einen Haufen, 13 ist die Mindestzahl, die wir erhalten.
Methoden zum Einstellen des Haufens (kleiner oberer Haufen):
Ein Haufen M -Elemente wird bereitgestellt. Nach Ausgabe der oberen Elemente des Haufens bleiben m-1-Elemente übrig. Das untere Element des Haufens wird an die Oberseite des Haufens gefüttert, und der Haufen wird zerstört, da der Wurzelknoten nicht den Eigenschaften des Haufens entspricht.
Tauschen Sie den Wurzelknoten mit kleineren Elementen in den linken und rechten Unterbäumen aus.
Wenn Sie mit dem linken Subtree ausgetauscht werden: Wenn der linke Subtree -Haufen beschädigt ist, wiederholen Sie die Methode (2).
Wenn Sie mit dem rechten Subtree ausgetauscht werden, wiederholen Sie die Methode (2), wenn der rechte Subtree -Haufen zerstört wird.
Führen Sie den oben genannten Austauschbetrieb bei Unterbäumen fort, die die Haufen Eigenschaften erst erfüllen, wenn die Blattknoten und der Haufen gebaut sind.
Um den Haufen anzupassen, müssen Sie nur die beschädigten Knoten berücksichtigen, und andere Knoten müssen nicht eingestellt werden.
Code -Implementierung (Java)
Führen Sie den Code aus und vergleichen Sie die Kommentare mit den obigen Beispielschritten zum Vergleich.
Paket com.Coder4j.main; öffentliche Klasse Heapsort { / ** * Einstellen auf einen kleinen oberen Haufen (das Ergebnis ist von groß nach klein nach dem Sortieren) * @param Array ist das zu angepasste Haufen -Array. tmp = Array [s]; int child = 2 * s + 1; // Die Position des linken untergeordneten Knotensystems.OUT.println ("Der zu angepasste Knoten ist: Array [" + s + "] =" + tmp); Während (Kind <Länge) {// Kind + 1 das richtige Kind ist und derzeit den Knoten anpasst // Wenn es ein rechtes Kind gibt und kleiner als das linke Kind ist, verwenden Sie das rechte Kind, um mit dem Knoten zu vergleichen, andernfalls verwenden Sie das linke Kind, wenn (Child + 1 <Länge && Array [Kind]> Array [Kind + 1]) {Child ++; } System.out.println ("wird mit dem untergeordneten Array [" + child + "] =" + Array [child] + "compare"); // Wenn das kleinere Kind kleiner als dieser Knoten ist, wenn (Array [s]> Array [Child]) {System.out.println ("Kind ist kleiner als es, Swap -Position"); Array [s] = Array [Kind]; // Bewegen Sie das kleinere Kind nach oben und ersetzen Sie den aktuellen Knoten, um S = Child anzupassen; // den angepassten Knoten in die ursprüngliche Position des jüngeren Kinderarrays [Child] = TMP bewegen; Child = 2 * S + 1; // Beurteilen Sie weiterhin, ob der zu angepasste Knoten weiter angepasst werden muss, wenn (unter (unter (untergeordnete) = Länge) {System.out.println ("Es gibt keine Kinder, die Anpassung ist vorbei"); } else {system.out.println ("weiter mit dem neuen Kind vergleichen"); } // weitermachen; } else {System.out.println ("Die Kinder sind älter als sie, die Anpassung ist vorbei"); Break; // Der aktuelle zu angepasste Knoten ist kleiner als seine linken und rechten Kinder und muss nicht eingestellt werden, direkt}}}/ ** * Einstellen auf einen großen oberen Haufen (das Ergebnis ist von klein bis groß nach dem Sortieren). HeapadjustB (int [] Array, int s, int länge) {int tmp = array [s]; int child = 2 * s + 1; // Die Position des linken untergeordneten Knotensystems.OUT.println ("Der zu angepasste Knoten ist: Array [" + s + "] =" + tmp); Während (Kind <Länge) {// Child + 1 das richtige Kind ist und derzeit den Knoten anpasst // Wenn es ein rechtes Kind gibt und es größer ist als das linke Kind, verwenden Sie das rechte Kind, um mit dem Knoten zu vergleichen, andernfalls verwenden Sie das linke Kind, wenn (Kind + 1 <Länge && Array [Child] <Child + 1]) {Child ++; } System.out.println ("wird mit dem untergeordneten Array [" + child + "] =" + Array [child] + "compare"); // Wenn das ältere Kind größer als dieser Knoten ist, wenn (Array [s] <array [child]) {System.out.println ("Kind ist größer als es, Swap -Position"); Array [s] = Array [Kind]; // Bewegen Sie das ältere Kind nach oben und ersetzen Sie den aktuellen Knoten, um S = Child anzupassen; // den angepassten Knoten in die ursprüngliche Position des älteren untergeordneten Arrays [Child] = TMP bewegen; Child = 2 * S + 1; // Beurteilen Sie weiterhin, ob der zu angepasste Knoten angepasst werden muss, wenn (unter (mindeste> = Länge) {System.out.println ("Es gibt keine Kinder, die Anpassung ist vorbei"); } else {system.out.println ("weiter mit dem neuen Kind vergleichen"); } // weitermachen; } else {System.out.println ("Die Kinder sind kleiner als sie, die Anpassung ist vorbei"); Break; // Der aktuelle zu angepasste Knoten ist größer als seine linken und rechten Kinder und beenden Sie direkt ohne Anpassung}}/ ** * Heap -Sortieralgorithmus * * @param Array * @param inverse wahr in umgekehrter Reihenfolge. 2, um jeden Knoten nach oben anzupassen, um dem Heap -System zu entsprechen.OUT.println ("Anfangshaufenstart"); für (int i = (array.length-1) / 2; i> = 0; i--) {if (inverse) {heapadjusts (Array, i, array.length); } else {heapadjustb (Array, i, array.length); }} System.out.println ("Anfangsheap -End"); für (int i = array.length-1; i> 0; i--) {// tauschen Sie das Heap-Top-Element H [0] und das letzte Element im Heap int tmp = array [i] aus; Array [i] = Array [0]; Array [0] = TMP; // Nach jedem Tausch das Heap -Top -Element und das letzte Element im Haufen muss der Haufen angepasst werden, wenn (inverse) {heapadjusts (Array, 0, i); } else {heapadjustb (Array, 0, i); }}} public static void main (String [] args) {int [] array = {49, 38, 65, 97, 76, 13, 27, 49}; Haufen (Array, Falsch); für (int i: array) {System.out.print (i + ""); }}}Auslaufergebnisse:
Der Knoten, der am Anfang des anfänglichen Haufens eingestellt werden soll, ist: Array [3] = 97 Das Kind ist mit dem Kinderarray kleiner [7] = 49 Das Kind ist mit dem Kind kleiner, und der Knoten, der am Ende der Anpassung angepasst wird, ist: Array [2] = 65 Das Kind ist kleiner mit dem Child -Array. = 38 Das Kind ist mit dem untergeordneten Array [3] = 49 Das Kind ist mit dem Kinderarray [0] = 49 Das Kind ist mit dem Kinderarray [2] = 13 Das Kind ist mit dem Child -Array [6] = 27 das Kind kleiner als die Austauschposition kleiner und es gibt kein Kind in der Austauschposition. Der nach der Einstellung angepasste Knoten ist: Array [0] = 97 Das Kind ist kleiner als das Kind. Das Kind ist kleiner als das Kind. Die Austauschposition vergleicht weiterhin mit dem neuen Kind. Das Kind ist Array [6] = 49 Das Kind ist kleiner als die Austauschposition, und es gibt kein Kind in der Austauschposition. Der nach der Einstellung angepasste Knoten ist: Array [0] = 97 Das Kind ist kleiner als das Kind. Das Kind ist kleiner als das Kind. Das Kind ist kleiner als das Kind. Das Kind ist Array [1] = 38 Das Kind ist kleiner als das Kind. Das Kind ist Array [3] = 49 Das Kind ist kleiner als das Kind. Das Kind ist kleiner als die Austauschposition. Der nach der Einstellung angepasste Knoten lautet: Array [0] = 65 Das Kind ist Array [1] = 49 Das Kind ist kleiner als das Kind und die Austauschposition wird weiterhin mit dem neuen Kind verglichen. Das Kind wird größer sein als das Kind. Der nach der Einstellung angepasste Knoten lautet: Array [0] = 76 Das Kind ist größer als das Kind. Der nach der Einstellung angepasste Knoten lautet: Array [0] = 76 Das Kind ist kleiner als das Kind. Der nach der Einstellung angepasste Knoten lautet: Array [0] = 49 Das Kind ist kleiner als das Kind. Der nach der Einstellung angepasste Knoten ist: Array [0] = 97 Das Kind ist kleiner als das Kind. Der nach der Einstellung angepasste Knoten ist: Array [0] = 97 76 65 49 49 38 27 13
PS: Der Unterschied zwischen der Sortierung von Haufen und der direkten Sortierung von Einfügen
Um den Datensatz mit dem kleinsten Schlüsselwort aus R [1..n] auszuwählen, muss der N-1-Vergleich in der direkten Auswahlreihenfolge durchgeführt werden, um den Datensatz mit dem kleinsten Schlüsselwort in R [2..N] auszuwählen, N-2-Vergleiche müssen durchgeführt werden. In den folgenden N-2-Vergleiche wurden möglicherweise viele Vergleiche in den vorherigen N-1-Vergleiche durchgeführt, aber da diese Vergleichsergebnisse nicht in der vorherigen Reihenfolge beibehalten wurden, wurden diese Vergleichsoperationen während der nächsten Ordnung wiederholt.
Die Heap -Sortierung kann einen Teil der Vergleichsergebnisse durch eine Baumstruktur speichern, die die Anzahl der Vergleiche verringern kann.