優先キュー！これを分解して、データ構造のこの部分について学びましょう。-＆＃＆チュートリアル-php.cn

Priority Queue! Vamos destrinchar e aprender sobre essa parte de Estrutura de Dados.

列

キューは、スタックと同様、リストを特殊化したものです。これは FIFO ベース (先入れ先出し) に基づいており、先入れ先出しが先出しであることを意味します。言い換えれば、列の「最年長」の人が最初に出発します。わかりやすくするために、銀行の列を考えてみましょう。

⚠️

キューアプリケーション: オペレーティングシステムでのプロセス管理。同時プログラミングにおけるタスク間の通信。コンピュータネットワーク（印刷）。 Web サーバー上のリクエストへの応答

キュー自体は、末端でのデータの直接操作のみを許可します。

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

ログイン後にコピー

優先キュー

これは、日常の一般的な行列の動作に似ていますが、ここで、あなたが銀行の列に並んでいて、女性が列に入るとき、彼女の年齢が高いほど優先順位が高いため、全員が彼女を先に行かせます。

Priority Queue データ構造では、各ノードには Key-Value があり、Key はその優先度を格納するキー、Value はノードの値です。 Java のデフォルトでは、キーは最初は数値であり、プログラマが後で変更できます。

KeyとValueのセットをEntryと呼ぶので、このE.Dのインターフェースが変わります。その他の詳細は次のとおりです。キーを定義した後は変更できません。 2 つのノードのキーの優先順位の値が同じ場合、プログラマがルールを選択します。

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

ログイン後にコピー

次の構造では、Node と Entry、first、last、size 属性、compareTo のクラスを使用します

優先キューは、ソート済み (Sorted Priority Queue) と未ソート (Unorted Priority Queue) の 2 つに分かれています

ソートされた優先キュー

順序付きリストは正しい位置にノードを挿入するため、削除は簡単です。最初のノードを削除するだけです (ED を行うプログラマが、最も優先度の高い要素を先頭に置く必要があると定義している場合)

どのノードが最も優先度が高いかを知るために、compareTo というコレクション関数を使用します。この関数は、戻り値が次の場合、この E.D の実行に重要な結果を得ることができます。

否定: メソッドを呼び出すオブジェクトが、パラメーターとして渡されたオブジェクトよりも「小さい」場合。
ゼロ: オブジェクトが等しい場合。
肯定: メソッドを呼び出すオブジェクトが、パラメーターとして渡されたオブジェクトよりも「大きい」場合。

入れる

参加するにはいくつかのことを確認する必要があります

最初のステップ → 新しいノードを作成します

Node newNode = new Node(key, value)

ログイン後にコピー

第 2 ステップ → キューが空かどうかを確認し、空の場合は、それが唯一であることを考慮して、Head と Last を新しいノードとして配置します

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

ログイン後にコピー

第 3 ステップ → それがリスト内の唯一の要素ではない場合は、最初のノードと比較して新しいノードの優先順位が高いかどうかを確認する必要があります。

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

ログイン後にコピー

第 3 ステップ → 次に、リストの最後の要素と比較します

Node newNode = new Node(key, value)

ログイン後にコピー

4 番目のステップ → 残りは全部ではないにしても、真ん中だけが残ります!これを行うには、newNode (nN) の前に補助ノードを作成して 2 つを比較する必要があります。auxNode が何も指さない場合、または nN が auxNode より大きい場合 (大きいため、nN が auxNode より大きい場合) に比較が終了します。列の後ろにいます）。この while は、aux が 2 つのノードの値を巡回して比較するために使用され、値を見つけると、nN を auxNode
の後ろに配置します。

        if(isEmpty()){
            first = newNode;
            last = newNode;
        }else{

ログイン後にコピー

取り除く

Sorted の削除メソッドは、すでに述べたようにキューがすでに編成されているため、はるかに簡単です。

第 1 ステップ → すべての Remove メソッドは削除する要素を返すため、このステップではエントリ (なぜノードではないのか) を作成します

         if(compare(newNode, first)<0){
                 //Se o nN for menor que o F
                 //Levando em consideração que a prioridade maior é 0
                 //Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
                newNode.next = first;
                first.previous = newNode;
                first = newNode;
          }

ログイン後にコピー

第 2 ステップ → 最初のノードを削除するので、First を First から次のノードにポイントするだけです

             }else if(compare(newNode, last)>=0){
           //Se o nN for maior que o L
           //Significa que o número de nN é maior que L
           //Então bota o nN para ultimo
                newNode.previous=last;
                last.next=newNode;
                last = newNode;
            }else{

ログイン後にコピー

第 3 ステップ → キューに要素が 1 つだけあるかどうかを確認します。要素が 1 つだけある場合、キューは空になります。次に、F と L を null に設定する必要があります

            }else{
                //se nao for nada, está no meio
                //entao temos que achar entre qual dos meios
                Node auxNode = first;
                while(compare(newNode, auxNode)>0 && auxNode.next!=null){
                    //enquanto o newNode tiver prioridade maior que o auxiliar
                    //e o auxiliar tiver um proximo
                    auxNode = auxNode.next;
                }
                newNode.next = auxNode;
                newNode.previous = auxNode.previous;
            }
        }

ログイン後にコピー

第 4 ステップ → それが唯一の要素ではないということは、他にも要素があるということです!したがって、ステップ 2 で最初のものを削除すると、以前は First だったものはまだ前のものによって接続されているため、次のことを行う必要があります。

        Entry<K,V> max = maxPriority();

ログイン後にコピー

最大優先度

リスト内で最も優先度の高い要素を返すメソッド。縦軸にあるため、最初の要素のみを返します。

        first = first.next;

ログイン後にコピー

漸近分析

Método	O(_)
size	O(1)
isEmpty	O(1)
insert	O(n)
remove	O(1)
maxPriority	O(1)

未ソートの優先キュー

乱れたキューは、順序付けられたものとは大きく異なります。彼のメソッドから始めましょう:

入れる

未分類、いいね、無秩序に追加するには、この新しい要素がどこにあるかを心配する必要はありません。最後に追加するだけです。

第 1 ステップ → リストが空かどうかを確認します。空であれば、追加されるノードは最初 (First) と最後 (Last) になります。

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

ログイン後にコピー

第 2 ステップ → 空でない場合は、最後にこのノードを追加するだけで問題ありません!

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

ログイン後にコピー

最大優先度

未ソートでの削除は、ソートでのわずかなコード行よりもはるかに複雑です…

「なぜ?」ご質問のとおり、maxPriority と呼ばれるメソッド (他のバージョンではこれもはるかに単純でした) を使用する必要があります。このメソッドの目的は、最高の優先度を持つノードを見つけることです。以前は、わずか数行のコードで簡単な方法で教えられていましたが、現在では、この最も優先度の高いノードが実際にどこにあるのかわからないため、キュー全体を調べてノードを探す必要があります。そのため、remove 自体を確認する前に、maxPriority を確認します。

第 1 ステップ → データ構造をトラバースしたいときは常に 2 つのノードが必要です。常に先に進むための補助的なノードと、達成したいノード (この場合は MaxPriority)

Node newNode = new Node(key, value)

ログイン後にコピー

第 2 ステップ → これら 2 つはノード内で実行され、aux が null (キューの終わり) に達したときにのみ終了します。これらのノードを比較し、それが負の場合は、aux が max よりも小さいことを意味するため、max が最大となり、max ノードの値を更新してから aux を実行します。

        if(isEmpty()){
            first = newNode;
            last = newNode;
        }else{

ログイン後にコピー

取り除く

最初のステップ → すべての emove で、削除されるノードを格納する変数を作成します。この場合、maxPriority
メソッドを呼び出しているため、どれが削除されるかはすでにわかっています。

         if(compare(newNode, first)<0){
                 //Se o nN for menor que o F
                 //Levando em consideração que a prioridade maior é 0
                 //Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
                newNode.next = first;
                first.previous = newNode;
                first = newNode;
          }

ログイン後にコピー

第 2 ステップ → それが唯一の要素であるかどうかを確認します。そうであれば、F と L は null です!

             }else if(compare(newNode, last)>=0){
           //Se o nN for maior que o L
           //Significa que o número de nN é maior que L
           //Então bota o nN para ultimo
                newNode.previous=last;
                last.next=newNode;
                last = newNode;
            }else{

ログイン後にコピー

第 3 ステップ → それが唯一のものでない場合は、他のオプションがあります。最大値が最後のものである場合は、最後を削除し、最初のものである場合は、最初のものを削除し、2 つまたは 2 つでもない場合は、その中にあります。真ん中です！

            }else{
                //se nao for nada, está no meio
                //entao temos que achar entre qual dos meios
                Node auxNode = first;
                while(compare(newNode, auxNode)>0 && auxNode.next!=null){
                    //enquanto o newNode tiver prioridade maior que o auxiliar
                    //e o auxiliar tiver um proximo
                    auxNode = auxNode.next;
                }
                newNode.next = auxNode;
                newNode.previous = auxNode.previous;
            }
        }

ログイン後にコピー

第 4 ステップ → 中央にある場合は、群衆の中にある最大値を削除する必要があります。これは、他の誰もそれを指していないときに発生します。