1. Grundwissen
Was wir normalerweise einen Haufen nennen, bezieht sich auf einen binären Haufen, der auch als vollständiger binärer Baum oder ungefähr vollständiger binärer Baum bezeichnet wird. Der binäre Haufen ist in den größten Haufen und den kleinsten Haufen unterteilt.
Die Heap -Sortierung bezieht sich auf einen Sortieralgorithmus, der unter Verwendung der Heap -Datenstruktur entwickelt wurde, was eine Art Sortierauswahl darstellt. Sie können schnell Elemente des angegebenen Index unter Verwendung der Eigenschaften des Arrays finden. Arrays können direkt auf dem Index basierende Elemente erhalten, und die zeitliche Komplexität beträgt O (1), dh Konstanten, sodass sie für die Wertschöpfung äußerst effizient sind.
Die Eigenschaften des maximalen Haufens sind wie folgt:
Die Eigenschaften des Mindesthaufens sind wie folgt:
2. Algorithmus dachte
1. Die Algorithmus -Idee des größten Haufens lautet:
Zunächst ist der anfängliche R [0… N-1] in den größten Haufen eingebaut. Zu diesem Zeitpunkt ist es ein ungeordneter Haufen. Das Heap-Top ist das größte Element und dann wird der letzte Rekord R [N-1] des ungeordneten Bereichs ausgetauscht. Dies führt zu dem neuen ungeordneten Bereich R [0… N-2] und dem geordneten Bereich R [N-1] und erfüllt R [0… N-2] .Keys ≤ r [n-1] .Key.
Da der erste R [0… N-2] die Eigenschaften des maximalen Haufens nach dem Austausch nicht erfüllt, wird der erste R [0… N-2] auf den maximalen Haufen eingestellt, bis nur das letzte Element von r [0] eingestellt ist.
Nach Abschluss der maximalen Haufensart handelt es sich tatsächlich um eine aufsteigende Sequenz. Jedes Mal, wenn der Haufen eingestellt wird, wird das größte Element erhalten und dann mit dem letzten Element des aktuellen Haufens ausgetauscht. Daher ist die endgültige Sequenz eine aufsteigende Sequenz.
2. Die Algorithmus -Idee des kleinsten Haufens lautet:
Zunächst ist der anfängliche R [0… N-1] in den kleinsten Haufen eingebaut. Zu diesem Zeitpunkt ist es ein ungeordneter Haufen. Das obere Element des Haufens ist das kleinste Element und tauscht dann den oberen R [0] mit dem letzten r [n-1] des ungeordneten Bereichs aus, wodurch der neue ungeordnete Haufen R [0… N-2] und den geordneten Heap r [n-1] und erfüllt r [0… n-2].
Da der erste R [0… N-2] die Eigenschaften des Mindesthaufens nach dem Austausch nicht erfüllen, wird der erste R [0… N-2] auf den minimalen Haufen eingestellt, bis nur das letzte Element von r [0] angepasst und der Mindesthaufen sortiert ist. Nachdem die Bestellung des Mindesthaufens abgeschlossen ist, handelt es sich tatsächlich um eine absteigende Sequenz. Jedes Mal, wenn der Haufen eingestellt wird, wird das kleinste Element erhalten und dann mit dem letzten Element des nicht ordneten Haufens ausgetauscht, sodass die erhaltene Sequenz in absteigender Reihenfolge ist.
TIPP: Der Prozess der Haufensortierung ist eigentlich der Prozess der kontinuierlichen Erweiterung des geordneten Bereichs und dann kontinuierlich reduziert den ungeordneten Bereich, bis nur geordnete Bereiche vorhanden sind.
3. Sortierungsprozessanalyse
Da der Algorithmus relativ abstrakt ist, veranschaulichen wir hier direkt den Prozess der Haufensortierung, indem wir ein kleines Beispiel geben. Als nächstes verwenden wir diese ungeordnete Sequenz, um den größten Haufen für die Heap -Sortierung zu verwenden, und die resultierende Sequenz ist die aufsteigende Sequenz (ASC).
Unordentliche Sequenz: 89, -7,999, -89,7,0, -888,7, -7
Schritt 1: Initialisieren Sie den maximalen zum Erstellen zu erstellenden Haufen:
Schritt 2: Tauschen Sie das maximale Element 999 oben auf dem Haufen mit dem letzten Element des ungeordneten Bereichs aus, damit 999 ein geordneter Bereich wird. Nach dem Austausch wird -7 zum Haufen. Da -7 nicht das größte Element im ungeordneten Bereich ist, ist es notwendig, den ungeordneten Bereich so anzupassen, dass der Maximalwert 89 im nicht ordneten Bereich zum Haufen der Oberseite wird, so dass -7 und 89 ausgetauscht werden. Nach dem Austausch entspricht der rechte Unterbaum von 89 nicht die Eigenschaften des größten Haufens, sodass der rechte Unterbaum auf den größten Haufen angepasst werden muss, so dass -7 mit 0 ausgetauscht werden muss, wie in der folgenden Abbildung gezeigt:
Aus der Abbildung ist der Swap -7% 89% der Stapel das größte Element, aber das linke Kind von -7 ist 0 und das rechte Kind -888. Da -7 <0 ist der Knoten -7 nicht den Eigenschaften des Haufens, und muss daher angepasst werden. Also wird 0 mit -7 ausgetauscht.
Wiederholen Sie dann den zweiten Schritt, bis er zu einem geordneten Bereich wird.
Schließlich: Was erhalten wird, ist eine aufsteigende Sequenz
4. Zeitkomplexität
Die Zeit der Haufensortierung besteht hauptsächlich aus dem Zeitaufwand des Erstellens des anfänglichen Haufens und der wiederholten Einstellung des Haufens. Da die Heap -Sortierung instabil ist, ist die Zeitkomplexität, die sie erhält, entsprechend der tatsächlichen Situation größer, sodass sie nur die durchschnittliche Zeitkomplexität dauern kann.
Die durchschnittliche Zeitkomplexität ist: O (N * log2 (n))
Zu den zeitaufwändigen Operationen der Haufensortierung gehören: anfängliche Heap + wiederholte Einstellung des Haufens, und die zeitliche Komplexität lautet wie folgt:
1. Erstes Heap -Gebäude: Jeder übergeordnete Knoten verglichen und tauschte sich mit den linken und rechten untergeordneten Knoten für bis zu zwei Mal aus, sodass die Komplexität mit der Anzahl der übergeordneten Knoten zusammenhängt. Basierend auf 2x <= n (x ist die Anzahl der Male n Elemente kann in zwei Hälften gefaltet werden, dh die Anzahl der übergeordneten Knoten), es wird x = log2n erhalten. Das heißt, o (log2n)
2. Wiederholte Einstellung des Haufens: Da die Array -Vergleichsergebnisse während der Initialisierung des Haufens aufgezeichnet werden, ist die Haufensart nicht empfindlich gegenüber der Reihenfolge des Arrays der ursprünglichen Sequenz, und die beste Situation ist dem schlimmsten Fall ähnlich. Das Heap-Top-Element muss n-1-Mal extrahiert werden. Jedes Mal, wenn das Heap -Top -Element genommen wird, muss der Haufen wieder aufgebaut werden (O (O (Rekonstruktion) <o (Anfangshaufen)). Also weniger als o (n-1) * o (log2n)
Empfohlene Nutzung:
Da die Häufigkeit der Initialisierung des Heaps verglichen werden muss, eignet sich die Haufenssorten besser für Situationen, in denen die Datenmenge sehr groß ist (Millionen Daten oder mehr). Da eine effiziente schnelle Sortierung auf einer rekursiven Implementierung basiert, tritt ein Stapelüberlauffehler auf, wenn das Datenvolumen sehr groß ist.
5. Java -Beispielcode
öffentliche Klasse Heapsort {private static int [] sort = new int [] {1,0,10,20,3,5,6,4,9,8,12, 17,34,11}; public static void main (String [] args) {BuildMaxheapify (sortieren); Haufen (sortieren); drucken (sortieren); } private statische Hohlraum-BuildMaxheapify (int [] data) {// Nur diejenigen ohne Kinder müssen den maximalen Heap erstellen, starten Sie vom letzten übergeordneten Knoten int startindex = getParentIndex (Daten.Länge-1); // Erstellen Sie das maximale Heap vom Ende und es ist das korrigierte Haufen für (int i = startIndex; i> = 0; i-). }}/***Erstellen Sie den maximalen Heap**@paramdata*@paramheapsize erfordert die Größe des maximalen Heaps, der im Allgemeinen verwendet wird, da der Maximalwert am Ende platziert wird. Das Ende wird nicht mehr als maximaler heap*@paramindex die Position, an der der Maximum -Haufen benötigt wird. der aktuelle Punkt mit den linken und rechten untergeordneten Knoten int links = getChildleftIndex (Index); int right = getChildrightIndex (Index); int größte = index; if (links <heapsize && data [index] <data [links]) {größte = links; } if (rechts <heapsize && daten [ } // Nach dem Erhalt des Höchstwerts muss er möglicherweise ausgetauscht werden. Wenn sie ausgetauscht werden, sind die Kinder möglicherweise nicht der größte Haufen. Es muss angepasst werden, wenn (größte! = Index) {int temp = data [index]; Daten [Index] = Daten [größtes]; Daten [größte] = temp; Maxheapify (Daten, heapsize, größte); }} /***Sortierung wird der Maximalwert am Ende platziert. Obwohl Daten der größte Heap sind, wird sie nach dem Sortieren von * *@paramdata */private statische Hohlhaufen (int [] Daten) {// Austausch mit dem Header am Ende den maximalen Heap nach dem Austausch für (int i = data.Length-1; i> 0; i-) {int temp = data [0] an. Daten [0] = Daten [i]; Daten [i] = temp; Maxheapify (Daten, i, 0); }} / ** *paramcurrent *@return * / private static int getParentIndex (int current) {return (current-1) >> 1; } / ** *Präsentieren Sie die untergeordnete Knotenposition auf Klammern, und die Additionspriorität ist höher * *@paramcurrent *@return * / private static int getChildleftIndex (int current) {return (aktuell << 1) +1; } / ** *Right Child Node Position * *@paramcurrent *@return * / private static int getChildrightIndex (int current) {return (current << 1) +2; } private static void print (int [] data) {int pre = -2; für (int i = 0; i <data.length; i ++) {if (pre <(int) getLog (i+1)) {pre = (int) getLog (i+1); System.out.println (); } System.out.print (Daten [i]+"|"); }}/** *Logo mit Basis 2 * *@paraparam *@return */private static double GetLog (Double Param) {return math.log (param) /math.log (2); }}