JavaScriptを介したバイナリヒープと優先度付きキュー
キューはスライスされたパン以来最もクールなものであることに誰もが同意できると確信していますが、実際には、ヒープと呼ばれるツリーのバリエーションと混合することではるかにうまくいくことができます。 ヒープを使用すると、データを、順序ではなく重要度で並べ替えられた、よりインテリジェントなキューに構造化できます。
コンセプト
バイナリ検索ツリーとは異なり、兄弟間で値を比較して整理しました。ヒープを使用すると、親と子の間でのみ機能します。 これにより、ヒープの2つの可能性、max heap
とmin heap
が得られ、最高値から最低値に移動するか、その逆に移動するかが決まります。 簡単にするために、最小ヒープに変換するのは非常に簡単なので、最大ヒープのみに焦点を当てます。
二分探索木と同様に、二分ヒープは親に対して2つ以下の子しか持つことができません。 また、すべての新しいノードが左から右にいっぱいになるまでレベルに追加されるため、常にバランスが取れているため、これらは特別です。
残念ながら、リンクリストは、通常は左右の子を持つツリーとして概念化されていますが、バイナリヒープには一般的に最適なアプローチではありませんが、それでも可能です。
ほとんどの場合、配列として処理する方がよいので、ここで説明します。 順序は、次のレベルに移動する前に、レベル上ですべてが左から右になっていると予想されるとおりです。
このようにして、ノードの子を見つけるための非常に一貫したパターンを作成します。 ノードの左側のすべての子は、親から2n + 1
離れた位置に正確に配置され、n
が親のインデックスであり、すべての右側の子が2n + 2
です。
ノードの追加
新しいノードを追加するのは、配列にプッシュするのと同じくらい簡単なように見えますが、注意が必要なのは、それ自体と最大値の間の親と比較して、それに応じて並べ替える必要があることです。
VisuAlgo.netのおかげでグラフィック/アニメーション
新しいアイテムを配列の最後にプッシュした後、より大きな値を「バブルアップ」する必要があります。 まず、配列の最後にある新しいアイテムを取得する必要があります。これをインデックスに分割し、そのインデックスに新しいアイテムを追加します。
アイテムを追加するたびに、子を見つけるための方程式の逆、(n-1)/2
を使用してその親を見つけます。 親が現在のノードよりも小さい場合は、それらを交換してから、次のcurrent
になるインデックスを保存します。 これは、親がなくなるまで続きます。
index
は最後から徐々に上に移動するので、ゼロより大きい限り、交換を続けます。
class BH { constructor() { this.values = []; } add(element) { this.values.push(element); let index = this.values.length - 1; const current = this.values[index]; while (index > 0) { let parentIndex = Math.floor((index - 1) / 2); let parent = this.values[parentIndex]; if (parent <= current) { this.values[parentIndex] = current; this.values[index] = parent; index = parentIndex; } else break; } } } const tree = new BH(); tree.add(3); tree.add(4); tree.add(31); tree.add(6); console.log(tree); // [31, 6, 4, 3]
マックスを削除
最上位ノードの削除は、想像するよりも少し複雑です。 最初のノードであるmaxを返し、最後のノードである配列の最後を取得して、それを新しいmaxとして設定します。
これを行うのは、比較と交換を途中で行いながら、ツリーの最下部に「沈む」ときに、他の値と比較するための簡単なベースラインとして最小値を使用できるようにするためです。
VisuAlgo.netのおかげでグラフィック/アニメーション
単純な部分は、現在の最大値を取得して、最後のアイテムと置き換える前にポップオフすることです。その後、他のすべてが完了した後、元の最大値を返すことができます。
開始インデックスを取得したら、その右と左の両方の子を取得します。 左の子が有効なアイテムであり、それより大きい場合は、swap
として保存して、すべての比較が完了したときにスワップを実行できます。
右の子はもう少し複雑です。1つだけ、そして最大の子を親と交換する必要があります。 rightChild
は、まだ定義されていないか、leftChild
より大きい場合にのみ、swap
として設定できるという別の要件を追加します。
class BH { extractMax() { const max = this.values[0]; const end = this.values.pop(); this.values[0] = end; let index = 0; const length = this.values.length; const current = this.values[0]; while (true) { let leftChildIndex = 2 * index + 1; let rightChildIndex = 2 * index + 2; let leftChild, rightChild; let swap = null; if (leftChildIndex < length) { leftChild = this.values[leftChildIndex]; if (leftChild > current) swap = leftChildIndex; } if (rightChildIndex < length) { rightChild = this.values[rightChildIndex]; if ( (swap === null && rightChild > current) || (swap !== null && rightChild > leftChild) ) swap = rightChildIndex; } if (swap === null) break; this.values[index] = this.values[swap]; this.values[swap] = current; index = swap; } return max; } } const tree = new BH(); tree.add(3); tree.add(4); tree.add(31); tree.add(6); console.log(tree.extractMax()); // 31
優先キュー
いくつかのマイナーな調整で、バイナリヒープをキューと混合し、データが追加されたときではなく、重要度によってデータを整理するタイプのキューを作成できます。
これは、単一の数値の代わりにノードを格納することで簡単に実現できます。 各ノードには優先度レベル(たとえば1〜5)があり、これを使用して順序を決定します。 2つのノードの優先度が同じである場合、左の子が最初に追加されるため、最初に移動します。
if
ステートメントで比較を行うたびに、ノードのpriority
を使用するだけです。
class Node { constructor(val, priority) { this.val = val; this.priority = priority; } } class PQ { constructor() { this.values = []; } enqueue(val, priority) { let newNode = new Node(val, priority); this.values.push(newNode); let index = this.values.length - 1; const current = this.values[index]; while (index > 0) { let parentIndex = Math.floor((index - 1) / 2); let parent = this.values[parentIndex]; if (parent.priority <= current.priority) { this.values[parentIndex] = current; this.values[index] = parent; index = parentIndex; } else break; } } dequeue() { const max = this.values[0]; const end = this.values.pop(); this.values[0] = end; let index = 0; const length = this.values.length; const current = this.values[0]; while (true) { let leftChildIndex = 2 * index + 1; let rightChildIndex = 2 * index + 2; let leftChild, rightChild; let swap = null; if (leftChildIndex < length) { leftChild = this.values[leftChildIndex]; if (leftChild.priority > current.priority) swap = leftChildIndex; } if (rightChildIndex < length) { rightChild = this.values[rightChildIndex]; if ( (swap === null && rightChild.priority > current.priority) || (swap !== null && rightChild.priority > leftChild.priority) ) swap = rightChildIndex; } if (swap === null) break; this.values[index] = this.values[swap]; this.values[swap] = current; index = swap; } return max; } } const tree = new BH(); tree.enqueue(3, 2); tree.enqueue(4, 5); tree.enqueue(31, 1); tree.enqueue(6, 3); console.log(tree.dequeue()); // 4 console.log(tree.dequeue()); // 6 console.log(tree.dequeue()); // 3 console.log(tree.dequeue()); // 31
まとめ
ツリートラバーサルの標準キューを使用したのと同じように、優先キューは、グラフやより複雑な構造をインテリジェントにトラバースするために不可欠です。
最大ヒープを最小ヒープに変換するのは、すべての比較で大なり値を小なり値に変更するのと同じくらい簡単です。