1. Ich muss über Binärbäume sprechen
Um den Heap zu verstehen, müssen Sie zunächst den Binärbaum verstehen. In der Informatik ist ein Binärbaum eine Baumstruktur, in der jeder Knoten höchstens zwei Unterbäume hat. Normalerweise werden Teilbäume als „linker Teilbaum“ und „rechter Teilbaum“ bezeichnet. Binärbäume werden häufig zur Implementierung binärer Suchbäume und binärer Heaps verwendet.
Jeder Knoten eines Binärbaums hat höchstens zwei Teilbäume (es gibt keine Knoten mit einem Grad größer als 2). Die Teilbäume eines Binärbaums sind in linke und rechte Teilbäume unterteilt, und die Reihenfolge kann nicht umgekehrt werden. Die i-te Ebene eines Binärbaums hat höchstens 2i – 1 Knoten; ein Binärbaum mit der Tiefe k hat höchstens 2k – 1 Knoten für jeden Binärbaum T, wenn die Anzahl der Endknoten n0 ist mit Grad 2 ist n2, dann ist n0 = n2 + 1.
Drei Hauptunterschiede zwischen Bäumen und Binärbäumen:
Die Anzahl der Knoten eines Baums muss mindestens 1 betragen, während die Anzahl der Knoten eines Binärbaums 0 betragen kann
Es gibt keine Begrenzung für den maximalen Grad eines Knotens in einem Baum, während der maximale Grad eines Knotens in einem Binärbaum 2 beträgt
Die Knoten des Baums sind nicht in links und rechts unterteilt, während die Knoten des Binärbaums in links und rechts unterteilt sind
Binärbäume werden in vollständige Binärbäume und vollständige Binärbäume unterteilt
Vollständiger Binärbaum: Ein Baum mit der Tiefe k und 2k – 1 Knoten wird als vollständiger Binärbaum bezeichnet
(vollständiger Binärbaum mit Tiefe 3)
Vollständiger Binärbaum: Ein Binärbaum mit der Tiefe k und n Knoten. Genau dann, wenn jeder seiner Knoten den Knoten mit den Nummern 1 bis n im vollständigen Binärbaum mit der Tiefe k entspricht, wird er als vollständiger Binärbaum bezeichnet
(vollständiger Binärbaum mit Tiefe 3)
2. Was ist ein Haufen?
Ein Heap (Binärheap) kann als vollständiger Binärbaum betrachtet werden. Eine „ausgezeichnete“ Eigenschaft eines vollständigen Binärbaums ist, dass jede Ebene außer der untersten Ebene voll ist, wodurch der Heap Arrays zur Darstellung (gewöhnlich) verwenden kann Binärbäume werden normalerweise durch verknüpfte Listen als Basiscontainer dargestellt. Jeder Knoten entspricht einem Element im Array.
Wie unten gezeigt, handelt es sich um die Beziehung zwischen einem Heap und einem Array
(Zusammenhang zwischen Heap und Array)
Für einen gegebenen Index i eines Knotens können die Indizes des übergeordneten Knotens und des untergeordneten Knotens dieses Knotens einfach berechnet werden:
Parent(i) = floor(i/2), der Index des übergeordneten Knotens von i
Left(i) = 2i, der Index des linken untergeordneten Knotens von i
Right(i) = 2i + 1, i ist der Index des rechten untergeordneten Knotens
Binäre Heaps werden im Allgemeinen in zwei Typen unterteilt: maximaler Heap und minimaler Heap.
Maximaler Heap:
Der maximale Elementwert im Max-Heap erscheint am Wurzelknoten (oben im Heap)
Der Elementwert jedes übergeordneten Knotens im Heap ist größer oder gleich seinem untergeordneten Knoten (falls vorhanden)
(maximaler Heap)
Mindestheap:
Der kleinste Elementwert im Min-Heap erscheint am Wurzelknoten (oben im Heap)
Der Elementwert jedes übergeordneten Knotens im Heap ist kleiner oder gleich seinem untergeordneten Knoten (falls vorhanden)
(min. Heap)
3. Heap-Sortierprinzip
Heap-Sortierung besteht darin, die maximale Anzahl an der Spitze des Heaps zu entfernen, den verbleibenden Heap weiter an den maximalen Heap anzupassen und die maximale Anzahl an der Spitze des Heaps erneut zu entfernen. Dieser Vorgang wird bis dahin fortgesetzt ist nur noch eine Zahl übrig. Definieren Sie die folgenden Operationen auf dem Heap:
Max-Heapify: Passen Sie die untergeordneten Endknoten des Heaps so an, dass die untergeordneten Knoten immer kleiner sind als der übergeordnete Knoten
Erstellen Sie einen maximalen Heap (Build-Max-Heap): Ordnen Sie alle Daten im Heap neu an, um ihn zu einem maximalen Heap zu machen
Heap-Sortierung: Entfernen Sie den Wurzelknoten der ersten Daten und führen Sie eine rekursive Operation zur maximalen Heap-Anpassung durch
Bevor wir mit der folgenden Diskussion fortfahren, muss darauf hingewiesen werden, dass Arrays alle nullbasiert sind, was bedeutet, dass sich unser Heap-Datenstrukturmodell ändern wird
(Nullbasiert)
Dementsprechend müssen auch einige Berechnungsformeln entsprechend angepasst werden:
Parent(i) = floor((i-1)/2), der Index des übergeordneten Knotens von i
Left(i) = 2i + 1, i ist der Index des linken untergeordneten Knotens
Right(i) = 2(i + 1), i ist der Index des rechten untergeordneten Knotens
Die Funktion der maximalen Heap-Anpassung (MAX-HEAPIFY) besteht darin, die Eigenschaften des maximalen Heaps beizubehalten und ist die Kernunterroutine zum Erstellen des maximalen Heaps. Der Funktionsprozess ist wie in der Abbildung dargestellt:
(Max-Heapify)
Da der Heap nach einer Anpassung immer noch gegen die Heap-Eigenschaften verstößt, sind rekursive Tests erforderlich, um sicherzustellen, dass der gesamte Heap die Heap-Eigenschaften erfüllt. Dies kann in JavaScript wie folgt ausgedrückt werden:
/**
* 从 index 开始检查并保持最大堆性质
*
* @array
*
* @index 检查的起始下标
*
* @heapSize 堆大小
*
**/
function 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, heapSize); // 递归调整
}
}
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
Im Allgemeinen wird Rekursion hauptsächlich in der Divide-and-Conquer-Methode verwendet, Divide-and-Conquer ist hier jedoch nicht erforderlich. Darüber hinaus erfordern rekursive Aufrufe das Schieben/Löschen des Stapels, was im Vergleich zur Iteration einen leichten Leistungsnachteil mit sich bringt. Nach der 20/80-Regel kann dies natürlich ignoriert werden. Wenn Sie jedoch das Gefühl haben, dass Sie sich bei der Verwendung der Rekursion unwohl fühlen, können Sie auch die Iteration verwenden, z. B. die folgende:
/**
* 从 index 开始检查并保持最大堆性质
*
* @array
*
* @index 检查的起始下标
*
* @heapSize 堆大小
*
**/
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;
}
}
}
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
Die Funktion zum Erstellen eines maximalen Heaps (Build-Max-Heap) besteht darin, ein Array in einen maximalen Heap umzuwandeln. Er akzeptiert zwei Parameter: Array und Heap-Größe rufen Max-Heapify von unten auf top. Transformieren Sie das Array und erstellen Sie einen maximalen Heap. Da Max-Heapify sicherstellen kann, dass die Knoten nach dem Knoten mit dem Index i die maximale Heap-Eigenschaft erfüllen, kann ein Bottom-up-Aufruf von Max-Heapify diese Eigenschaft während des Transformationsprozesses beibehalten. Wenn die Anzahl der Elemente im maximalen Heap n beträgt, beginnt Build-Max-Heap bei Parent(n) und ruft Max-Heapify aufwärts auf. Der Vorgang ist wie folgt:
In JavaScript wie folgt beschrieben:
function buildMaxHeap(array, heapSize) {
var i,
iParent = Math.floor((heapSize - 1) / 2);
for (i = iParent; i >= 0; i--) {
maxHeapify(array, i, heapSize);
}
}
Heap-Sort ist der Schnittstellenalgorithmus der Heap-Sortierung, der zuerst Build-Max-Heap aufruft, um das Array in einen maximalen Heap umzuwandeln, dann die oberen und unteren Elemente des Heaps auszutauschen und dann das untere anzuheben Rufen Sie schließlich Max-Heapify auf, um die maximalen Heap-Eigenschaften beizubehalten. Da das oberste Element des Heaps das größte Element im Heap sein muss, wird nach einer Operation das größte im Heap vorhandene Element vom Heap getrennt. Nach n-1-maliger Wiederholung wird das Array angeordnet. Der gesamte Vorgang läuft wie folgt ab:
In JavaScript wie folgt beschrieben:
function heapSort(array, heapSize) {
buildMaxHeap(array, heapSize);
for (int i = heapSize - 1; i > 0; i--) {
swap(array, 0, i);
maxHeapify(array, 0, i);
}
}
4.JavaScript-Sprachimplementierung
Abschließend organisieren Sie das Obige wie folgt in den vollständigen Javascript-Code:
function heapSort(array) {
function 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;
}
}
}
function buildMaxHeap(array) {
var i,
iParent = Math.floor(array.length / 2) - 1;
for (i = iParent; i >= 0; i--) {
maxHeapify(array, i, array.length);
}
}
function sort(array) {
buildMaxHeap(array);
for (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) Algorithmusleistung/-komplexität
Die zeitliche Komplexität der Heap-Sortierung ist sehr stabil (wir können sehen, dass sie nicht empfindlich auf die Eingabedaten reagiert) und ist O(n㏒n)-Komplexität. Der beste Fall ist derselbe wie der schlechteste Fall.
Die räumliche Komplexität variiert jedoch von Implementierung zu Implementierung. Zwei häufige Komplexitäten wurden oben diskutiert: O(n) und O(1). Im Einklang mit dem Prinzip der Platzersparnis empfehle ich die O(1)-Komplexitätsmethode.
(2) Algorithmusstabilität
Heap-Sortierung umfasst eine große Anzahl von Screening- und Verschiebungsprozessen und ist ein instabiler Sortieralgorithmus.
(3) Algorithmus-anwendbare Szenarien
Heap-Sortierung verursacht einen relativ großen Aufwand beim Einrichten und Anpassen des Heaps und ist nicht geeignet, wenn nur wenige Elemente vorhanden sind. Es ist jedoch immer noch eine gute Wahl, wenn viele Elemente vorhanden sind. Insbesondere bei der Lösung von Problemen wie „die ersten n größten Zahlen“ ist es fast der bevorzugte Algorithmus.
