JavaScript で Priority Queue を実装する

1. 優先キューの紹介

通常のキューに要素が挿入されると、データはバックエンドに配置され、前の要素がすべて処理されるまで前のデータは処理されないことがわかっています。ただし、優先キューは要素を挿入するときにデータの優先度を考慮し、それを他のデータの優先度と比較します。比較が完了すると、キュー内のこの要素の正しい位置を取得できます。その他の処理方法は、基本的に基本キューと同じです。

優先キューに関して考慮すべき主な問題は次のとおりです。

各要素は単なるデータではなく、データの優先順位も含みます。
addメソッドでは、優先度に応じて正しい位置に配置します。

病院（救急科）の待合室など日常生活でも優先待ち行列が利用されている例があります。医師はより重篤な症状の患者を優先するだろう。コンピュータでは、優先度キューを使用して、キュー内のタスクの順序を並べ替えることもできます。たとえば、各スレッドで処理されるタスクの重要度は異なり、優先度のサイズを使用して、キュー内でスレッドが処理される順序を決定できます。

2. 優先キューのカプセル化

優先キューの動作は基本的にキューと同じですが、挿入操作が異なるため、ここでは優先キューの挿入操作を中心に実装します。

たとえば、特定のデータの優先度に応じて要素を挿入する場合、まず優先度キューをカプセル化するクラスを作成し、その中に要素の優先度とデータを保存するコンストラクターを作成し、次に要素を格納する属性を追加します。

コードは次のとおりです。

関数PtiorityQueue(){
            var アイテム = [];
            //要素とその優先度を保存するための新しいコンストラクタをカプセル化します function queueElement(element,priority){
                this.element = 要素;
                this.priority = 優先度;
            }
        }

作成が完了すると、挿入操作が実装されます。

キューに要素がない場合は直接挿入する
挿入する要素の優先度がキュー内の要素の優先度よりも低い場合は、ソート後に挿入されます。

具体的な実装コードは次のとおりです。

関数PtiorityQueue(){
   this.items = [];
    //要素とその優先度を保存するための新しいコンストラクタをカプセル化します function QueueElement(element,priority){
        this.element = 要素;
        this.priority = 優先度;
    }
     //1. 挿入メソッドを実装する PtiorityQueue.prototype.enqueue = function(element,priority){
        //1. queueElement オブジェクトを作成する var queueElement = new QueueElement(element,priority);
        //2. キューが空かどうかを判定する if (this.items.length == 0) {
            this.items.push(キュー要素);
        }それ以外{
            var フラグ = false;
            for(var i =0;i<this.items.length;i++){
                キュー要素の優先度が this.items[i].priority より低い場合
                    this.items.splice(i,0,queueElement);
                    フラグ = true;
                    壊す;
                }
            }
            if(!フラグ){
                this.items.push(キュー要素)
            }
        }
     }
}

入力テストデータは次のとおりです。