JavaScriptにおける "データ構造 "ヒープの実装

ヒープとは？

ヒープとは、コンピュータ・サイエンスにおける特殊な木のようなデータ構造のこと。ヒープ内の任意のノードPとCが与えられたとき、PがCの親ノードであれば、Pの値はCの値以下になる」という性質を満たす場合にヒープと呼ぶことができます。

親ノードの値が子ノードの値以下である場合、このヒープは最小ヒープと呼ばれます；

逆に、親ノードの値が常に子ノードの値以上である場合、このヒープは最大ヒープと呼ばれます。

ヒープの一番上にあるノードはルート・ノードと呼ばれ、それ自身の親ノードを持ちません。

なぜヒープが必要なのか

ヒープは、O(1)の時間複雑度でヒープ内の最大値または最小値を得ることができます。一方、配列や連鎖リストはO(n)の時間複雑度を必要とします。2進数の場合はO(log n)の時間複雑度が必要です。

ヒープを実装するには？

ヒープは木のような構造ですが、ヒープを配列に変換することも可能です。

上の図をよく見てください。最大の要素と最小の要素は、O(1)の時間複雑度で得られるように、index= 0に置かれます。そして、インデックスが , に等しいノードのインデックスとその子のインデックスは , .

ヒープ内の親ノード・インデックスと子ノード・インデックスの関係を要約すると、以下のようになります：

もちろん、子ノードのインデックスを使って親ノードのインデックスを反転させることも可能です。 親インデックス= Math.floor(サブノードのインデックス / 2)

MinHeap

class MinHeap {
 constructor () {
 this.heap = []
 }
 getMin () {
 // 最小値はスタックの一番上にある
 return this.heap[0]
 }
}

insert

1. insert(10)、ヒープが空、10がルートノードとして使用されます。
2. insert(23), 23 > 10, 23は10の子になります。
3. insert(36), 36 > 10, 36は10の子になります。
4. < 23，18不能作为23的子节点。所以18和23需要调换位置。接着继续向上查找，18 > insert(18)、18が10なので、18は10の子になります。

挿入メソッドの実装

class MinHeap {
 // ....
 getParentNode (index) {
 return this.heap[Math.floor(index / 2)]
 } 
 insert (node) {
 this.heap.push(node)
 if (this.heap.length > 1) {
 let currentIndex = this.heap.length - 1
 // を調べる必要がある。
 while (
 currentIndex > 1 &&
 this.getParentNode(currentIndex) > this.heap[currentIndex]
 ) {
 // MinHeapでは、親ノードが子ノードより大きい場合、親ノードと子ノードを互いに入れ替える必要がある。
 // 親ノードのインデックス
 const parentIndex = Math.floor(currentIndex / 2)
 let temp = this.heap[parentIndex]
 this.heap[parentIndex] = this.heap[currentIndex]
 this.heap[currentIndex] = temp
 currentIndex = parentIndex
 }
 }
 }
}

remove

最小ヒープ内のノードを削除し、ルートノードを削除した後、ヒープ内の最後のビットをルートノードに移動します。次に、ルートノードと子ノードのサイズを順番に比較し、ルートノードが子ノードより大きい場合は、子ノードとルートノードの位置を入れ替えます。すべての比較が完了するまで

class MinHeap {
 // ...
 remove () {
 let min = this.getMin()
 if (this.heap.length > 2) {
 this.heap[1] = this.heap[this.heap.length - 1]
 this.heap.splice(this.heap.length - 1)
 // 配列にノードが2つしかない場合、すべての子を順番に比較せずに、2つのノードを直接比較する。
 if (this.heap.length === 3) {
 if (this.heap[1] > this.heap[2]) {
 let temp = this.heap[1]
 this.heap[1] = this.heap[2]
 this.heap[2] = temp
 }
 return min
 }
 let currentIndex = 1
 // 最初の要素はNULLなので、1は追加されない
 let leftChildIndex = currentIndex * 2
 let rightChildIndex = currentIndex * 2 + 1
 // ノードが2つ以上ある場合、親ノードは左右の子ノードを比較する必要がある。
 while (
 this.heap[leftChildIndex] &&
 this.heap[rightChildIndex] &&
 (this.heap[currentIndex] > this.heap[leftChildIndex] || this.heap[currentIndex] > this.heap[rightChildIndex])
 ) {
 if (this.heap[leftChildIndex] < this.heap[rightChildIndex]) {
 let temp = this.heap[currentIndex]
 this.heap[currentIndex] = this.heap[leftChildIndex] 
 this.heap[leftChildIndex] = temp
 currentIndex = leftChildIndex
 } else {
 let temp = this.heap[currentIndex]
 this.heap[currentIndex] = this.heap[rightChildIndex]
 this.heap[rightChildIndex] = temp
 currentIndex = rightChildIndex
 }
 leftChildIndex = currentIndex * 2
 rightChildIndex = currentIndex * 2 + 1
 }
 } else if (this.heap.length === 2) {
 // ノードが1つしかない場合はルートノードを削除する。
 this.heap.splice(1, 1)
 } else {
 return null
 }
 return min
 }
}

MinHeap 完全な実装

class MinHeap {
 constructor () {
 this.heap = [null]
 }
 getMin () {
 return this.heap[1]
 }
 getParentNode (index) {
 return this.heap[Math.floor(index / 2)]
 } 
 insert (node) {
 this.heap.push(node)
 if (this.heap.length > 1) {
 let currentIndex = this.heap.length - 1
 // を調べる必要がある。
 while (
 currentIndex > 1 &&
 this.getParentNode(currentIndex) > this.heap[currentIndex]
 ) {
 // MinHeapでは、親ノードが子ノードより大きい場合、親ノードと子ノードを互いに入れ替える必要がある。
 // 親ノードのインデックス
 const parentIndex = Math.floor(currentIndex / 2)
 let temp = this.heap[parentIndex]
 this.heap[parentIndex] = this.heap[currentIndex]
 this.heap[currentIndex] = temp
 currentIndex = parentIndex
 }
 }
 }
 remove () {
 let min = this.getMin()
 if (this.heap.length > 2) {
 this.heap[1] = this.heap[this.heap.length - 1]
 this.heap.splice(this.heap.length - 1)
 // 配列にノードが2つしかない場合、すべての子を順番に比較せずに、2つのノードを直接比較する。
 if (this.heap.length === 3) {
 if (this.heap[1] > this.heap[2]) {
 let temp = this.heap[1]
 this.heap[1] = this.heap[2]
 this.heap[2] = temp
 }
 return min
 }
 let currentIndex = 1
 // 最初の要素はNULLなので、1は追加されない
 let leftChildIndex = currentIndex * 2
 let rightChildIndex = currentIndex * 2 + 1
 // ノードが2つ以上ある場合、親ノードは左右の子ノードを比較する必要がある。
 while (
 this.heap[leftChildIndex] &&
 this.heap[rightChildIndex] &&
 (this.heap[currentIndex] > this.heap[leftChildIndex] || this.heap[currentIndex] > this.heap[rightChildIndex])
 ) {
 if (this.heap[leftChildIndex] < this.heap[rightChildIndex]) {
 let temp = this.heap[currentIndex]
 this.heap[currentIndex] = this.heap[leftChildIndex] 
 this.heap[leftChildIndex] = temp
 currentIndex = leftChildIndex
 } else {
 let temp = this.heap[currentIndex]
 this.heap[currentIndex] = this.heap[rightChildIndex]
 this.heap[rightChildIndex] = temp
 currentIndex = rightChildIndex
 }
 leftChildIndex = currentIndex * 2
 rightChildIndex = currentIndex * 2 + 1
 }
 } else if (this.heap.length === 2) {
 // ノードが1つしかない場合はルートノードを削除する。
 this.heap.splice(1, 1)
 } else {
 return null
 }
 return min
 }
}

実際の応用：配列のK番目に大きい要素

トピック

ソートされていない配列のk番目に大きい要素を見つける。k番目に異なる要素ではなく、ソートされた配列のk番目に大きい要素を見つける必要があることに注意する。
例1:
 : [3,2,1,5,6,4] とk= 2
 : 5
例2:
 : [3,2,3,1,2,4,5,5,6] とk= 4
 : 4

解

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
 if (nums.length == 0) {
 return -1
 }
 
 if (nums.length < k) {
 return -1
 }
 
 const heap = new MinHeap()
 let result = null
 
 for (let i = 0; i < nums.length; i++) {
 heap.insert(nums[i])
 }
 
 // トピックは、対応する最小要素に変換できる最大の要素である。
 // マックスヒープを直接使うことも可能である
 k = nums.length - k + 1
 
 while (k > 0) {
 result = heap.remove()
 k -= 1
 }
 
 return result
};