ヒープのJavaScript実装方法を詳しく解説

ヒープの定義

最大(最小)ヒープは、各ノードのキー値がその子のキー値(存在する場合)以上(より大きい)であるツリーです。大きな上部ヒープは完全なバイナリ ツリーであり、最大ツリーでもあります。ミニヒープは完全なバイナリ ツリーであり、最小ツリーでもあります。

さらに、これら 2 つの概念を覚えておくことはコードを書く上で非常に重要です:

1. 親ノードと子ノードの間の関係: 定義を参照

2. 完全なバイナリ ツリー: [2] を参照

基本操作

1. ビルド (ヒープの構築)

2. 挿入

3. 削除 (削除: 最小または最大のもの)

コードの実装

まず、非常に重要なことが 2 つありますコードを書く前のポイント:

1. 配列はヒープの記憶構造として使用でき、非常にシンプルで操作が簡単です。 2. さらに、配列は記憶構造として使用されるため、親間の関係がわかります。子ノードはインデックスに基づいて簡単に決定できます。

JavaScript の場合、配列インデックスとして 0 から始まる関係は次のとおりです:

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

前述の 2 つの概念を理解すると役立ちます:

1. 配列であるため、その関係親ノードと子ノードの間 特別な構造を維持する必要はなく、インデックス間の計算によって取得できるため、手間が大幅に軽減されます。リンク リスト構造の場合は、さらに複雑になります。

2. 完全なバイナリ ツリーの概念は、次のノードの前に左から右に埋める必要があります。これにより、配列を変更して全体を大きく動かす必要がなくなります。これは、ランダム ストレージ構造 (配列) の欠点でもあります。要素を削除した後、要素全体を前方に移動すると、より時間がかかります。また、この機能により、要素を削除するときにヒープが最後のリーフ ノードをルート ノードに追加します。 コードの実装:

/******************************************************
* 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();

JavaScript に関するいくつかの概要を以下に示します。エレガントすぎるように感じます。これより良い表現方法と記述方法があるかどうかはわかりません。

配列の使用法をいくつか学びました。プッシュ操作とポップ操作はとても使いやすいです。も一時的にインターネットから検索されました (instanceof)。これを使用しないと、次回からは忘れてしまうでしょう。

参考

[1]「データ構造とアルゴリズム解析:C言語記述」

[2]グラフィカルデータ構造(8) - バイナリヒープ

[3]>データ構造:ヒープ

まとめ

JavaScript の配列はプッシュおよびポップ操作を実装しており、他の多くの言語でも同様のデータ構造と操作 (C++ の Vector など) が提供されており、ランダム操作もサポートされています。そこで、これらの構造に自動ソートの概念を追加すれば、簡単にヒープを解決できるのではないかと思い始めました。その後、C++ STL の make_heap を見て、自分の知識が少なすぎることに気づきました。私の考え方が正しかったと思います。私は JavaScript を確認しませんでしたが、JavaScript は存在​​するか実装が簡単だと思います。実際に実装してみると、この構造も非常に単純であることがわかりました。一度詳しく触れてみるつもりであれば、

JavaScript の詳細はまだわかっていません。たとえば、JavaScript を使用する前に、配列のアプリケーションについて詳しく読む必要があります。 、そして本質には継続的な学習と練習が必要です

これらのコードは、概念とプログラミングを理解している限り、基本を書き出すことができます。ただし、コードはより簡潔に記述することができます。たとえば、削除関数が最小の子ノードを見つけた場合、左側のノードのインデックスが小さい必要はありません。コード部分は今後も最適化と合理化ができそうな気がします。