JavaScriptを介したバイナリヒープと優先度付きキュー

投稿日: 2022-04-20 2022-10-06
タグ: 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 としてのみ設定できます swap まだ定義されていない場合、または leftChild.

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つのノードの優先度が同じである場合、左の子が最初に追加されるため、最初に移動します。

私たちがしなければならないのは、ノードのを使用することだけです priority で比較するたびに if 声明。

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

まとめ

ツリートラバーサルの標準キューを使用したのと同じように、優先キューは、グラフやより複雑な構造をインテリジェントにトラバースするために不可欠です。

最大ヒープを最小ヒープに変換するのは、すべての比較で大なり値を小なり値に変更するのと同じくらい簡単です。

getdocs

13036