1. Ich muss über binäre Bäume sprechen
Um den Haufen zu verstehen, müssen Sie zuerst den binären Baum verstehen. In der Informatik ist ein binärer Baum eine Baumstruktur mit höchstens zwei Unterbäumen pro Knoten. Normalerweise werden Unterbaume als "linker Subtree" und "rechter Subtree" bezeichnet. Binärbäume werden häufig verwendet, um binäre Suchbäume und binäre Haufen implementieren.
Jeder Knoten eines Binärbaums hat höchstens zwei Unterbäume (Knoten mit Grad größer als 2). Die Unterbälde eines binären Baums können nach links und rechts unterteilt werden, und die Reihenfolge kann nicht umgekehrt werden. Die I -Th -Schicht des binären Baums hat höchstens 2i -1 -Knoten; Der binäre Baum mit einer Tiefe von K hat höchstens 2K -1 -Knoten; Bei einem Binärbaum t, wenn die Anzahl der Anschlussknoten n0 ist und die Anzahl der Knoten mit einem Grad von 2 N2 ist, n0 = n2 + 1.
Es gibt drei Hauptunterschiede zwischen einem Baum und einem binären Baum:
Die Anzahl der Knoten im Baum beträgt mindestens 1, während die Anzahl der Knoten im binären Baum 0 sein kann.
Der maximale Grad der Knoten im Baum ist keine Grenze, während der maximale Knotengrad im binären Baum 2 beträgt
Es gibt keinen Unterschied zwischen links und rechts in den Knoten eines Baumes, während es keinen Unterschied zwischen links und rechts in den Knoten eines binären Baumes gibt.
Binärbäume sind in komplette binäre Bäume und volle binäre Bäume unterteilt.
Voller Binärbaum: Ein Baum mit einer Tiefe von K und 2K - 1 Knoten wird als voller binärer Baum bezeichnet
(Voller binärer Baum mit Tiefe 3)
Kompletter binärer Baum: Ein binärer Baum mit n Knoten mit Tiefe k. Es wird nur dann als vollständiger binärer Baum bezeichnet, wenn jeder seiner Knoten einem Knoten mit Sequenznummern von 1 bis n in einem vollständigen binären Baum mit Tiefe k entspricht.
(Voller binärer Baum mit Tiefe 3)
2. Was ist ein Haufen?
Ein Haufen (binärer Haufen) kann als vollständiger binärer Baum angesehen werden. Eine "ausgezeichnete" Eigenschaft eines vollständigen Binärbaums ist, dass mit Ausnahme der unteren Schicht jede Schicht voll ist, wodurch der Haufen durch ein Array dargestellt werden kann (gewöhnliche allgemeine Binärbäume werden normalerweise durch verknüpfte Listen als Basisbehälter dargestellt), und jeder Knoten entspricht einem Element im Array.
Die folgende Abbildung zeigt die Beziehung zwischen einem Haufen und einem Array
(Die Beziehung zwischen Haufen und Array)
Für den angegebenen Index I eines Knotens kann es leicht für den Index des übergeordneten Knotens und des untergeordneten Knotens dieses Knotens berechnet werden:
Elternteil (i) = Boden (I/2), der übergeordnete Knoten -Index von i
Links (i) = 2i, das linke untergeordnete Knoten -Index von i
Richtig (i) = 2i + 1, der richtige Unterschiedsnoten -Index von i
Es gibt im Allgemeinen zwei Arten von binären Haufen: den größten Haufen und den kleinsten Haufen.
Maximale Haufen:
Der maximale Elementwert im maximalen Heap erscheint am Stammknoten (oben auf dem Haufen)
Der Elementwert jedes übergeordneten Knotens im Heap ist größer oder gleich seines untergeordneten Knotens (falls vorhanden)
(Maximaler Haufen)
Mindesthaufen:
Der minimale Elementwert im minimalen Heap erscheint am Stammknoten (oben auf dem Haufen)
Der Elementwert jedes übergeordneten Knotens im Heap ist geringer als oder gleich seinem untergeordneten Knoten (falls vorhanden)
(Mindeststapel)
3. Prinzip der Haufenssorption
Die Heapsortierung besteht darin, die maximale Zahl am oberen Rand des maximalen Haufens herauszunehmen, den verbleibenden Haufen weiter auf den maximalen Haufen einzustellen und die maximale Zahl am oberen Rand des Haufens erneut herauszunehmen. Dieser Vorgang dauert fort, bis nur noch eine Nummer vorhanden ist. Definieren Sie die folgenden Operationen im Haufen:
Max-Heapifizierung: Passen Sie den Endknoten des Haufens an, damit der untergeordnete Knoten immer kleiner ist als der übergeordnete Knoten
Erstellen Sie einen maximalen Heap (Build-MAX-HEAP): Alle Daten des Haufens neu ordnen, um den maximalen Haufen zu machen
Heap-Sort: Entfernen Sie den Stammknoten der ersten Daten und führen Sie rekursiv
Bevor die folgende Diskussion fortgesetzt wird, ist ein Problem, das beachtet werden muss, ist: Die Arrays sind alle auf Null basiert, was bedeutet, dass sich unser Heap-Datenstrukturmodell ändert.
(Null basierend)
Entsprechend müssen auch mehrere Berechnungsformeln entsprechend angepasst werden:
Eltern (i) = Boden ((i-1)/2), der übergeordnete Knoten-Index von i
Links (i) = 2i + 1, das linke untergeordnete Knoten -Index von i
Richtig (i) = 2 (i + 1), der richtige Untergangs -Einweis für Kinder von i
Die Funktion der maximalen Haufenanpassung (Maxheapify) besteht darin, die Eigenschaften des größten Haufens aufrechtzuerhalten, und ist die Kernunterroutine zur Schaffung des größten Haufens. Der Betriebsprozess ist in der Abbildung dargestellt:
(Max-heapify)
Da der Haufen nach einer Anpassung immer noch gegen die Haufen Natur verstößt, ist rekursive Tests erforderlich, damit der gesamte Haufen die Haufen Natur erfüllt. Es kann in JavaScript wie folgt ausgedrückt werden:
/** * Überprüfen Sie den Index und führen Sie die maximalen Heap -Eigenschaften aus und verwalten Sie den Startindex der @Index -Prüfung * * @heapsize Heap -Größe * **/Funktion maxheapify (Array, Index, HeapSize) {var iMax = index, ileft = 2 * index + 1, iright = 2 * (Index + 1); if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft; } if (iright <heapsize && array [iMax] <array [iright]) {imax = iright; } if (IMAX! = INDEX) {SWAP (Array, IMAX, INDEX); Maxheapify (Array, IMAX, Heapsezize); // rekursive Einstellung}} Funktionswap (Array, i, j) {var temp = array [i]; Array [i] = Array [j]; Array [j] = temp;}Im Allgemeinen wird die Rekursion hauptsächlich in der Methode der Aufteilung und Behandlung verwendet, und hier besteht keine Notwendigkeit für Aufteilung und Behandlung. Darüber hinaus erfordern rekursive Anrufe Stapelpressung/Löschen, was im Vergleich zur Iteration einen leichten Leistungsnachteil aufweist. Dies kann natürlich gemäß der 20/80 -Regel ignoriert werden. Wenn Sie jedoch der Meinung sind, dass Sie die Verwendung von Rekursion Sie unwohl fühlen, können Sie auch Iteration verwenden, z. B. die folgenden:
/** * Überprüfen Sie den Index und führen Sie die maximalen Heap -Eigenschaften bei * * @Array * * Der Startindex des @Index -Checks * * @heapsize Heap -Größe * **/Funktion maxheapify (Array, Index, Heapsize) {var iMax, ileft, iright; while (true) {imax = index; Ileft = 2 * Index + 1; Iright = 2 * (Index + 1); if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft; } if (iright <heapsize && array [iMax] <array [iright]) {imax = iright; } if (IMAX! = INDEX) {SWAP (Array, IMAX, INDEX); Index = IMAX; } else {break; }}} Funktionswap (Array, i, j) {var temp = array [i]; Array [i] = Array [j]; Array [j] = temp;}Der Zweck der Erstellung eines maximalen Haufens (Build-MAX-HEAP) besteht darin, ein Array in einen maximalen Haufen umzuwandeln und zwei Parameter von Array und Haufen zu akzeptieren. Build-max-heap ruft max-heapify von unten nach oben, um das Array zu transformieren und den maximalen Haufen zu erstellen. Da Max-Hapify sicherstellen kann, dass die Knoten nach dem Abonnement die Eigenschaften des größten Haufens erfüllen, kann Bottom-up-Aufruf bei maximaler Haken diese Eigenschaft während des Transformationsprozesses beibehalten. Wenn das maximale Heap-Zahl-Element n ist, ruft Build-MAX-HEAP maximal-heapifiziert nach sequenz von übergeordnet (n) auf. Der Prozess ist wie folgt:
Die Beschreibung lautet wie folgt in JavaScript:
Funktion BuildMaxheap (Array, Heapsesize) {var i, iParent = math.floor ((heapsize - 1) / 2); für (i = iParent; i> = 0; i--) {maxheapify (Array, i, heapsize); }}Heap-Sort ist der Grenzflächenalgorithmus für die Heapsortierung. Heap-Sort ruft zuerst Build-MAX-HEAP auf, um das Array in den maximalen Haufen zu verwandeln, und tauscht dann die oberen und unteren Elemente des Haufens aus, steigt dann den Boden auf und ruft schließlich maximal heapifiziert, um die maximalen Haufen Eigenschaften aufrechtzuerhalten. Da das obere Element des Haufens das größte Element im Haufen sein muss, ist nach einem Vorgang das größte Element, das im Haufen vorhanden ist, vom Haufen vom Haufen getrennt, und nach wiederholtem N-1-mal wird das Array angeordnet. Der gesamte Prozess ist wie folgt:
Die Beschreibung lautet wie folgt in JavaScript:
Funktion Heapsort (Array, Heapsesize) {BuildMaxheap (Array, HeapSize); für (int i = heapsize-1; i> 0; i--) {Swap (Array, 0, i); Maxheapify (Array, 0, i); }}4. Implementierung von JavaScript -Sprache
Organisieren Sie schließlich die oben genannten in den vollständigen JavaScript -Code wie folgt:
Funktion Heapsort (Array) {Funktion Swap (Array, i, j) {var temp = array [i]; Array [i] = Array [j]; Array [j] = temp; } function maxheapify (Array, Index, heapsize) {var iMax, ileft, iright; while (true) {imax = index; Ileft = 2 * Index + 1; Iright = 2 * (Index + 1); if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft; } if (iright <heapsize && array [iMax] <array [iright]) {imax = iright; } if (IMAX! = INDEX) {SWAP (Array, IMAX, INDEX); Index = IMAX; } else {break; }}} Funktion BuildMaxheap (Array) {var i, iParent = math.floor (Array.length / 2) - 1; für (i = iParent; i> = 0; i--) {maxheapify (array, i, array.length); }} Funktionsart (Array) {BuildMaxheap (Array); für (var i = array.length-1; i> 0; i--) {Swap (Array, 0, i); Maxheapify (Array, 0, i); } return Array; } return sort (array);}5. Anwendung des Heap -Sortieralgorithmus
(1) Algorithmus Leistung/Komplexität
Die zeitliche Komplexität der Heap -Sortierung ist sehr stabil (wir können sehen, dass sie nicht empfindlich gegenüber Eingabedaten ist) und ist die Komplexität von O (NN), der beste Fall ist der gleiche wie der schlimmste Fall.
Die räumliche Komplexität variiert jedoch je nach Implementierung. Die obigen diskutiert zwei häufige Komplexitäten: O (n) und O (1). Basierend auf dem Prinzip des Speicherplatzes empfehle ich die Komplexitätsmethode O (1).
(2) Algorithmusstabilität
Es gibt eine große Anzahl von Filter- und Bewegungsprozessen im Haufensortieren, die zu einem instabilen Sortieralgorithmus gehört.
(3) Algorithmus anwendbares Szenario
Die Heap -Sortierung entsteht im Aufbau des Haufens und des Einstellens des Haufens relativ großer Overhead, und es gilt nicht, wenn es nur wenige Elemente gibt. Wenn es jedoch viele Elemente gibt, ist es immer noch eine gute Wahl. Insbesondere bei der Lösung von Problemen wie "die Anzahl der Top n groß" ist es fast der bevorzugte Algorithmus.