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.

/******************************************************
* 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

Referenz

[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;