ヒープとは?

ヒープは完全二分木の特別な種類です。完全二分木の各レベルはノードで完全に満たされ、最後のレベルでは、完全でない場合、右側のノードの数だけが欠落しています。

• 最大ヒープ：すべてのノードが子ノード以上

• 最小ヒープ：すべてのノードが子ノード以下

JS

JSは通常、ヒープを表現するために配列を使用します。

• 左の子ノードの位置は2*index + 1です。
• 右の子ノードの位置は2*index + 2です。
• 親ノードの位置は/2

最小ヒープ・クラスの実装： クラスの中で、要素を保持する配列を宣言します。主なメソッド：挿入、ヒープの先頭の削除、ヒープの先頭の取得、ヒープ・サイズの取得

要素を挿入します：

• ヒープの一番下、つまり配列の最後に値を挿入します。
• 親がこの挿入値以下になるまで、この値と親を入れ替えます。
• サイズkのヒープに要素を挿入する時間の複雑さはO(logk)

ヒープの先頭を削除します：

• ヒープの先頭を配列の末尾要素に置換
• 次に下に移動します。新しいヒープ・トップとその子ヒープを、子ヒープがこの新しいヒープ・トップ以上になるまで入れ替えます。
• サイズKのヒープにおいて、ヒープの先頭を削除する時間の複雑さはO(logk)

トップを取れ

• 配列の先頭を返します。

ヒープのサイズを取得します：

• 配列の長さを返します。

class MinHeap{
 constructor(){
 this.heap = [];
 }
 getParentIndex(index){
 return Math.floor((index - 1) / 2); //(index -1) >> 1
 }
 swap(i1, i2){
 let temp = this.heap[i1];
 this.heap[i1] = this.heap[i2];
 this.heap[i2] = temp;
 }
 shiftUp(index){
 if(index == 0){
 return;
 }
 const parentIndex = this.getParentIndex(index);
 if (this.heap[parentIndex] > this.heap[index]) {
 this.swap(parentIndex, index);
 this.shiftUp(parentIndex);
 }
 }
 insert(value){
 this.heap.push(value);
 this.shiftUp(this.heap.length - 1);
 }
 getLeftIndex(index){
 return 2 * index + 1;
 }
 getRightIndex(index){
 return 2 * index + 2;
 }
 shiftDown(index){
 let leftIndex = this.getLeftIndex(index);
 let rightIndex = this.getRightIndex(index);
 if (this.heap[leftIndex] < this.heap[index]){
 this.swap(leftIndex, index);
 this.shiftDown(leftIndex);
 }
 if (this.heap[rightIndex] < this.heap[index]) {
 this.swap(rightIndex, index);
 this.shiftDown(rightIndex);
 }
 }
 shift(){
 this.heap[0] = this.heap.pop();
 this.shiftDown(0);
 }
 peek(){
 return this.heap[0];
 }
 size(){
 return this.heap.length;
 }
}
let minHeap = new MinHeap();
minHeap.insert(3);
minHeap.insert(2);
minHeap.insert(1);
minHeap.shift();

ヒープの応用

ヒープは時間複雑さO(1)で効率的かつ迅速に最大値と最小値を見つけます。

K番目に大きい要素を見つける

• 1.最小ヒープを構築し、要素を順番にヒープに挿入します。
• 2、ヒープの容量がKを超えたら、ヒープの先頭を削除
• 3.挿入終了時、ヒープの先頭はK番目の最大要素

知識ソース：