Die Heap -Sortierung bezieht sich auf einen Sortieralgorithmus, der unter Verwendung der Heap -Datenstruktur entwickelt wurde. Das Stapeln ist eine Struktur, die ungefähr vollständig binärer Baum ist und die Eigenschaften des Stapelns erfüllt: Das heißt, der Schlüsselwert oder der Index eines untergeordneten Knotens ist immer kleiner als der übergeordnete Knoten.
Die durchschnittliche Zeitkomplexität der Heap -Sortierung beträgt (NLOGN).
Algorithmus Schritte:
1. Erstellen Sie einen Heap H [0..N-1]
2. Tauschen Sie den Haufenkopf (maximal) und den Haufenschwanz aus
3. Reduzieren Sie die Haufengröße um 1 und rufen Sie Shift_down (0) auf. Ziel ist es, die oberen Daten des Neuarrays an die entsprechende Position anzupassen.
4. Wiederholen Sie Schritt 2 bis die Größe des Haufens 1 beträgt 1
Haufen:
Der Haufen ist eigentlich ein völlig binärer Baum, und jeder Nicht-Blattknoten seines Nicht-Blattknotens erfüllt seine Eigenschaften: Schlüssel [i] <= Schlüssel [2i+1] && Schlüssel [i] <= Schlüssel [2i+2] oder Schlüssel [i]> = Schlüssel [2i+1] && Taste [2i+2]. Der Haufen ist in einen großen oberen Haufen und einen kleinen oberen Haufen unterteilt. Ein zufriedenstellender Schlüssel [i]> = Schlüssel [2i+1] && Schlüssel> = Schlüssel [2i+2] wird als großer oberer Haufen bezeichnet. Ein zufriedenstellender Schlüssel [i] <= Schlüssel [2i+1] && Key [i] <= Key [2i+2] wird als kleiner oberer Haufen bezeichnet. Aus den obigen Eigenschaften können wir erkennen, dass die Schlüsselwörter oben auf dem großen oberen Haufen definitiv die größten aller Schlüsselwörter sind und die Schlüsselwörter oben auf dem kleinen oberen Haufen die kleinsten aller Schlüsselwörter sind.
Haufenssortenidee:
Die Funktion des größten Schlüsselworts (Mindestschlüsselwort), das oben auf dem großen oberen Haufen (kleiner oberer Heap) aufgezeichnet wird, erleichtert die Auswahl des größten Datensatzes (Mindestdatensatz) von Störungen jedes Mal. Die Grundidee ist (Big Top Heap): 1) Konstruieren Sie die anfängliche Abfolge der zu sortierten Schlüsselwörter (R1, R2… .RN) in einen großen oberen Haufen, was der anfängliche gestörte Bereich ist; 2) Tauschen Sie das Heap-Top-Element R [1] mit dem letzten Element R [n] aus und erhalten Sie dann einen neuen ungeordneten Bereich (R1, R2,… RN-1) und eine neue geordnete Region (RN) und erfüllen R [1,2… N-1] <= R [N]; 3) Da der neue Heap-Top R [1] nach dem Austausch gegen die Eigenschaften des Haufens verstoßen kann, ist es erforderlich, den aktuellen ungeordneten Bereich (R1, R2,… RN-1) an einen neuen Haufen anzupassen und dann R [1] mit dem letzten Element der gestörten Fläche zu tauschen, um eine neue störte Fläche zu erhalten (R1, R2, R2, R2) und eine neue ordentliche Region (Rn-1, R2, R2). Wiederholen Sie diesen Vorgang, bis die Anzahl der Elemente im geordneten Bereich N-1 ist und der gesamte Sortiervorgang abgeschlossen ist. Der Betriebsprozess ist wie folgt: 1) Initialisieren Sie den Haufen: Konstrukt R [1..N] als Haufen; 2) Tauschen Sie das Heap -Top -Element R [1] des aktuellen ungeordneten Bereichs mit dem letzten Rekord im Intervall aus und stellen Sie dann den neuen ungeordneten Bereich an einen neuen Haufen ein. Daher sind die beiden wichtigsten Vorgänge für die Haufenssorgung den anfänglichen Haufen und die Einstellung des Haufens. Tatsächlich ist das Erstellen des anfänglichen Haufens tatsächlich ein Prozess der Einstellung des Haufens, aber das Erstellen des anfänglichen Haufens besteht darin, alle nicht-blattlichen Knoten einzustellen.
Ein Beispiel für die Illustration
Bei einem Formungsarray A [] = {16,7,3,20,17,8} sortieren Sie es. Erstellen Sie zunächst einen vollständigen binären Baum basierend auf dem Array -Element und erhalten Sie
Anschließend müssen Sie den anfänglichen Haufen erstellen und dann die Einstellung vom letzten Nicht-Blattknoten starten. Der Anpassungsprozess ist wie folgt:
Nach dem Austausch von 20 und 16 bewirkt 16, dass 16 die Eigenschaften des Haufens nicht begegnen, sodass es neu angepasst werden muss.
Dies gibt den anfänglichen Haufen.
Wenn es zuerst eingestellt wird, wird es zu einem großen oberen Stapel.
Das heißt, jede Einstellung besteht darin, den größten aus dem übergeordneten Knoten, des linken untergeordneten Knotens und des rechten untergeordneten Knotens zum Austausch mit dem übergeordneten Knoten auszuwählen (nach dem Austausch kann der ausgetauschte Kinderknoten dazu führen, dass der untergeordnete Knoten ausgetauscht wird, um nicht die Art des Heaps zu erfüllen, sodass der ausgetauschte Kinderknoten nach jedem Austausch erneut angepasst werden muss). Mit dem anfänglichen Haufen können Sie es sortieren.
Zu diesem Zeitpunkt befindet sich 3 oben auf dem Stapel und die Eigenschaften sind nicht voller Stapel. Sie müssen sich einstellen und weiter einstellen.
Auf diese Weise ist das gesamte Intervall bereits ordentlich. Aus dem obigen Vorgang können wir sehen, dass die Haufensortierung tatsächlich eine Art Auswahlsortierung ist, eine Baumauswahlsortierung. Um die Reihenfolge direkt auszuwählen, um den maximalen Datensatz aus R [1 ... n] auszuwählen, müssen die N-1-Zeiten verglichen werden und dann den maximalen Datensatz aus R [1 ... n-2] auswählen, müssen die N-2-mal verglichen werden. Tatsächlich wurden viele dieser N-2-Vergleiche in den vorherigen N-1-Vergleiche durchgeführt, und die Sortierung der Baumauswahl verwendet nur die Eigenschaften des Baumes, um einige der vorherigen Vergleichsergebnisse zu retten, sodass die Anzahl der Vergleiche reduziert werden kann. Für N -Schlüsselwortsequenzen muss jeder Knoten im schlimmsten Fall log2 (n) -Zeiten vergleichen, sodass seine schlimmste Fallzeitkomplexität nLog ist. Die Heap -Sortierung ist eine instabile Sortierung und ist nicht zum Sortieren mit weniger Datensätzen geeignet. So viel wurde oben beschrieben. Kurz gesagt, die grundlegende Praxis der Haufensortierung lautet: Verwenden Sie zunächst die Originaldaten, um einen großen (kleinen) Haufen als ursprünglich ungeordneten Bereich zu erstellen, und dann jedes Mal, wenn das Haufen -Top -Element herausgenommen und in den geordneten Bereich platziert wird. Da das obere Element des Haufens herausgenommen wird, setzen wir das letzte Element in den Haufen in die Oberseite des Haufens, sodass die Eigenschaften des Haufens zerstört werden. Wir müssen den Haufen neu einstellen und n-mal fortsetzen, dann werden n Elemente im nicht ordneten Bereich in den geordneten Bereich eingebracht, und der Sortiervorgang wird abgeschlossen.
(Der Gebäudestapel ist von unten nach oben)
Praktische Anwendung:
In der Praxis führen wir die Haufenssorten durch, um den maximalen oder minimalen Wert unter bestimmten Bedingungen zu erhalten. Zum Beispiel: 10 maximale Werte müssen zwischen 100 Zahlen gefunden werden. Daher definieren wir einen Haufen der Größe 10, bauen die ersten zehn Daten in 100 in einen kleinen oberen Haufen (die Oberseite des Haufens) und vergleichen sie dann mit der Oberseite des Haufens aus den 11. Daten in 100 Daten. Wenn die Oberseite des Haufens kleiner als die aktuellen Daten ist, wird die Oberseite des Haufens angezeigt, drücken Sie die aktuellen Daten in die Oberseite des Haufens und verschieben Sie die Daten von der Oberseite des Haufens auf eine bestimmte Position.
Code:
public class test0 {static int [] arr; // Heap -Array, gültiges Array public test0 (int m) {arr = new int [m];} static int m = 0; static int size = 0; // Wird verwendet, um gültige Daten im Heap public void addtosmall (int v) {// int [] a = zu markieren {16,4,5,9,1,10,11,12,13,14,15,2,6,6,7,8,111,222,333,555,66,67,54}; // Die Größe der Haufen ist 10 // arr = neu int [10]; if (Größe <arr.length) {arr [size] = v; add_sort (Größe); // add_sort1 (Größe); Größe ++;} else {arr [0] = v; i = 0; i <size; i ++) {System.out.println (arr [i]);}} public void del () {size-; arr [0] = arr [9]; add_sort1 (0);} public void klein (int int Index) {if (m <arr.length) {add_sort (index); m ++;} else {add_sort1 (index); m ++;}} public void add_sort (int index) {// Small Top Heap, Build Heap/ * übergeordnete Knotenkoordinaten: Index * links unterkleidet. Linke Kind*Wenn das letzte im Array gerade ist, ist es das rechte Kind, wenn der Kinderknoten größer als der übergeordnete Knoten ist, wird der Wertaustausch durchgeführt. Wenn das rechte Kind größer als das linke Kind ist, wird der Wertaustausch durchgeführt.**/Int par; if (index! dex] <arr [par]) {swap (arr, index, par);} add_sort (par);}} else {par = index/2; if (arr [index] <arr [par]) {SWAP (arr, index); par*2+1); if (arr [index] <arr [par]) {SWAP (arr, index, par);} add_sort (par);}}}} public void add_sort1 (int index) {// kleine obere heap/*oberen nach unten einstellen adjed down max = 0; if (links <10 && arr [links] <arr [index]) {max = links;} else {max = index;} if (rechts <10 && arr [rechts] <arr [max]) {max = rechts;} if (max! Importieren Sie java.util.scanner; public class main_test0 {public static void main (String args []) {Scanner scan = neuer Scanner (System.in); System.out.println ("Small Top Heap) Bitte geben Sie die Heap -Größe ein:"); {16,4,5,9,1,10,11,12,13,14,15,2,3,6,7,8}; für (int i = 0; i <A.Length; i ++) {test.addtosMall (a [i]);} test.printsmall ();Das obige Beispiel für Java Heap Sorting (Big Top Heap, Small Top Heap) ist der gesamte Inhalt, den ich mit Ihnen teile. Ich hoffe, Sie können Ihnen eine Referenz geben und ich hoffe, Sie können wulin.com mehr unterstützen.