Detaillierte Erläuterung der JavaScript-Implementierungsmethode von Heap

Definition von Heap

Ein maximaler (minimaler) Heap ist ein Baum, in dem der Schlüsselwert jedes Knotens nicht kleiner (größer) als der Schlüsselwert seines untergeordneten Knotens (falls vorhanden) ist ). Der Big-Top-Heap ist ein vollständiger Binärbaum und auch ein Maximumbaum. Der Mini-Heap ist ein vollständig binärer Baum und auch ein minimaler Baum.

Darüber hinaus ist es sehr wichtig, sich diese beiden Konzepte beim Schreiben von Code zu merken:

1. Die Beziehung zwischen übergeordneten Knoten und untergeordneten Knoten: siehe Definition

2 . Vollständiger Binärbaum: Referenz [2]

Grundoperationen

1. Erstellen (Build-Heap)

2. Einfügen(Einfügung )

3. Löschen (Löschen: das kleinste oder das größte)

Code-Implementierung

Zuallererst gibt es zwei Wichtige Dinge vor dem Schreiben von Code:

1. Ein Array kann als Speicherstruktur des Heaps verwendet werden, was sehr einfach und leicht zu bedienen ist

2. In Da das Array außerdem als Speicherstruktur verwendet wird, können die Beziehungen zwischen Vater und Sohn anhand des Index leicht gefunden werden.

Für JavaScript, beginnend mit 0 als Array-Index, ist die Beziehung wie folgt:

nLeftIndex = 2 * (nFatherIndex+1) - 1;
nRightIndex = 2* (nFatherIndex+1);

Es ist hilfreich zu verstehen:

1. Weil Da es sich um ein Array handelt, ist für die Aufrechterhaltung der Beziehung zwischen übergeordneten und untergeordneten Knoten keine spezielle Struktur erforderlich. Die Indizes können durch Berechnung ermittelt werden, was viel Aufwand erspart. Wenn es sich um eine verknüpfte Listenstruktur handelt, ist es viel komplizierter.

2. Das Konzept eines vollständigen Binärbaums kann auf [2] verwiesen werden von links nach rechts, bevor die nächste Ebene gefüllt werden kann. Dadurch wird sichergestellt, dass keine großen Bereiche des gesamten Arrays verschoben werden müssen. Dies ist auch ein Manko zufälliger Speicherstrukturen (Arrays): Nach dem Löschen eines Elements ist es zeitaufwändiger, das gesamte Element nach vorne zu verschieben. Diese Funktion bewirkt auch, dass der Heap beim Löschen von Elementen den letzten Blattknoten zum Wurzelknoten des Baums hinzufügt

Code-Implementierung:

/******************************************************
* file : 堆
* author : "page"
* time : "2016/11/02"
*******************************************************/
function Heap()
{
 this.data = [];
}
 
Heap.prototype.print = function () {
 console.log("Heap: " + this.data);
}
 
Heap.prototype.build = function(data){
 // 初始化
 this.data = [];
 if (!data instanceof Array)
 return false;
 
 // 入堆
 for (var i = 0; i < data.length; ++i) {
 this.insert(data[i]);
 }
 
 return true;
}
 
Heap.prototype.insert = function( nValue ){
 if (!this.data instanceof Array) {
 this.data = [];
 }
 
 this.data.push(nValue);
 // 更新新节点
 var nIndex = this.data.length-1;
 var nFatherIndex = Math.floor((nIndex-1)/2);
 while (nFatherIndex > 0){
 if (this.data[nIndex] < this.data[nFatherIndex]) {
 var temp = this.data[nIndex];
 this.data[nIndex] = this.data[nFatherIndex];
 this.data[nFatherIndex] = temp;
 }
 
 nIndex = nFatherIndex;
 nFatherIndex = Math.floor((nIndex-1)/2);
 }
}
 
Heap.prototype.delete = function( ){
 if (!this.data instanceof Array) {
 return null;
 }
 
 var nIndex = 0;
 var nValue = this.data[nIndex];
 var nMaxIndex = this.data.length-1;
 // 更新新节点
 var nLeaf = this.data.pop();
 this.data[nIndex] = nLeaf;
 
 while (nIndex < nMaxIndex ){
 var nLeftIndex = 2 * (nIndex+1) - 1;
 var nRightIndex = 2 * (nIndex+1);
 
 // 找最小的一个子节点(nLeftIndex < nRightIndex)
 var nSelectIndex = nLeftIndex;
 if (nRightIndex < nMaxIndex) {
 nSelectIndex = (this.data[nLeftIndex] > this.data[nRightIndex]) ? nRightIndex : nLeftIndex;
 }
 
 if (nSelectIndex < nMaxIndex && this.data[nIndex] > this.data[nSelectIndex] ){
 var temp = this.data[nIndex];
 this.data[nIndex] = this.data[nSelectIndex];
 this.data[nSelectIndex] = temp;
 }
 
 nIndex = nSelectIndex;
 }
 
 return nValue;
}
// test
var heap = new Heap();
heap.build([1, 3, 5, 11, 4, 6, 7, 12, 15, 10, 9, 8]);
heap.print();
// insert
heap.insert(2);
heap.print();
// delete
heap.delete();
heap.print();

Einige Zusammenfassung über JavaScript

Hier ist eine objektorientierte Implementierungsmethode. Es fühlt sich nicht allzu elegant an. Ich weiß nicht, ob es eine bessere Darstellungsmethode und Schreibmethode gibt ;

Ich habe mehrere Verwendungsmöglichkeiten von Arrays gelernt: Die Push- und Pop-Operationen sind so einfach zu verwenden

Die Methode zur Beurteilung von Arrays wurde auch vorübergehend im Internet gesucht ( Instanz von ), nicht sehr beeindruckend. Wenn ich es nicht benutze, vergesse ich es beim nächsten Mal vielleicht.

Referenz

[1] „Datenstruktur und Algorithmusanalyse: C-Sprachbeschreibung“

[2] Grafische Datenstruktur (8) – Binärer Heap

[3]>Datenstruktur: Heap

Zusammenfassung

Das Array von JavaScript implementiert Push- und Pop-Operationen, und viele andere Sprachen bieten ebenfalls ähnliche Datenstrukturen und Operationen (z. B C++'s Vector) und unterstützt auch Zufallsoperationen. Also begann ich zu denken, dass ein Heap leicht gelöst werden kann, wenn man diesen Strukturen einfach das Konzept der automatischen Sortierung hinzufügt. Als ich später den make_heap von C++ STL sah, wurde mir klar, dass ich zu wenig wusste, aber das wusste ich Ich bin froh, dass meine Denkweise richtig war. Ich habe JavaScript nicht überprüft, ich denke, es existiert oder ist einfach zu implementieren;

Nachdem ich es selbst implementiert habe, stellte ich fest, dass diese Struktur auch sehr einfach ist, solange man bereit ist, sich einmal intensiv damit auseinanderzusetzen ;

Ich weiß immer noch nicht viel über die Details von JavaScript. Ich muss zum Beispiel noch mehr Informationen über die Anwendung von Arrays lesen, bevor ich es verwenden kann , und das Wesentliche erfordert kontinuierliches Lernen und Üben.

Solange Sie die Konzepte und Grundlagen der Programmierung verstehen, können Sie sie schreiben. Der Code kann jedoch prägnanter geschrieben werden. Wenn die Löschfunktion beispielsweise den kleinsten untergeordneten Knoten findet, müssen die Indizes des linken und rechten Knotens nicht verglichen werden. Der Codeteil scheint noch weiter optimiert und verschlankt werden zu können.