優先キュー

単純だが非効率的な優先度キューは、様々な方法で作成できる。こうした素朴な実装は、優先度キューの期待される動作をより分かりやすく示すことができる。

• ソートされていない配列に要素を挿入し、最も優先度の高い要素を検索して抽出する。

  パフォーマンス: " insert" は${\displaystyle O(1)}$定数時間で「extract_max」は${\displaystyle O(n)}$線形時間。

挿入（要素、優先度）： node.element ← element node.priority ← 優先度 リストにノードを追加する extract_max (): 最高値 ← 0 リスト内の各ノードについて： 最高優先度 < ノード優先度の場合: 最高←ノード リスト.remove(highest) 最高位の要素を返す

• ソート済み配列に要素を挿入し、最初の要素 を取り出す

  パフォーマンス: " insert" は${\displaystyle O(n)}$線形時間で「extract_max」は${\displaystyle O(1)}$一定時間。

挿入（要素、優先度）： node.element ← element node.priority ← 優先度 for i in [0...N]: 要素 ← リスト.get_at_index(i) element.priority < node.priority の場合: list.insert_at_index(node, i + 1) 戻る extract_max (): 最高値 ← list.get_at_index(0) リスト.remove(highest) 最高位の要素を返す

パフォーマンスを向上させるために、優先度キューは通常ヒープに基づいており、${\displaystyle O(\log n)}$挿入および取り外しのパフォーマンス、${\displaystyle O(n)}$最初にヒープをセットから構築する${\displaystyle n}$要素。ペアリングヒープやフィボナッチヒープなどの基本ヒープデータ構造の変種は、一部の操作に対してより良い境界を提供することができる。^{[ 6 ]}

あるいは、自己平衡二分探索木を使用する場合、挿入と削除も${\displaystyle O(\log n)}$既存の要素のシーケンスからツリーを構築するには時間がかかるが、${\displaystyle O(n\log n)}$時間。これは、サードパーティライブラリや標準ライブラリなど、これらのデータ構造に既にアクセスできる場合によく見られます。空間計算量の観点からは、リンクリストを使用した自己平衡二分探索木を使用すると、他のノードへの追加の参照を保存する必要があるため、より多くのストレージが必要になります。

計算複雑性の観点から見ると、優先度付きキューはソートアルゴリズムと同等です。以下の「優先度付きキューとソートアルゴリズムの等価性」のセクションでは、効率的なソートアルゴリズムが効率的な優先度付きキューをどのように生成できるかを説明します。

特定のキータイプ、特に整数キーに対して、追加の操作を提供したり、ヒープベースの実装よりも優れたパフォーマンスを発揮したりする、いくつかの特殊なヒープデータ構造が存在します。可能なキーの集合が次のようになっているとします。${\displaystyle \{1,2,...,C\}}$。

• と のみが必要でinsert、かつ整数優先度の場合、バケットキューはの配列として構築できます。find-minextract-min${\displaystyle C}$連結リストとポインタ${\displaystyle {\text{top}}}$最初は${\displaystyle C}$キー付きアイテムの挿入${\displaystyle k}$アイテムを${\displaystyle k}$'th リスト、および更新情報${\displaystyle {\text{top}}\gets {\text{min}}({\text{top}},k)}$どちらも定数時間で実行されます。extract-minインデックスのリストから1つの項目を削除して返します。${\displaystyle {\text{top}}}$、次に増分${\displaystyle {\text{top}}}$必要に応じて、再び空でないリストを指すまで。${\displaystyle O(C)}$最悪の場合、時間。これらのキューは、グラフの頂点を次数でソートするのに役立ちます。^{[ 7 ]： 374}
• van Emde Boas ツリーはminimum、、、、、、、、および操作maximumをサポートします。insertdeletesearchextract-minextract-maxpredecessorsuccessor]${\displaystyle O(\log \log C)}$時間、ただし小さなキューには約のスペースコストがかかります${\displaystyle O(2^{m/2})}$、 どこ${\displaystyle m}$は優先度値のビット数です。^{[ 8 ]}ハッシュ化によりスペースを大幅に削減できます。
• フレッドマンとウィラードによるフュージョンツリーは、以下の操作を実装しています。minimum${\displaystyle O(1)}$時間insertとextract-minオペレーション${\displaystyle O(\log n/\log \log C)}$時間。しかし、著者は「我々のアルゴリズムは理論的な興味しか持たず、実行時間に関わる定数係数が実用性を妨げる」と述べている。^{[ 9 ]}

各操作に対して多数の「ピーク」操作を実行するアプリケーションの場合extract-min、ピークアクションの時間計算量は以下のように削減できます。${\displaystyle O(1)}$ツリーおよびヒープの実装では、挿入および削除のたびに最優先要素をキャッシュすることで、すべての実装においてこの問題を解決します。挿入の場合、新しく挿入された要素は以前にキャッシュされた最小要素と比較されるだけなので、追加されるコストは最大でも定数です。削除の場合、追加されるコストは最大でも「ピーク」コストですが、これは通常削除コストよりも安いため、全体の時間計算量に大きな影響はありません。

単調優先度キューは、挿入される項目が、以前に取り出された項目よりも優先度が低い（最小ヒープの場合）ことが決してないという状況に最適化された特殊なキューです。この制約は、優先度キューのいくつかの実用的な応用例で満たされています。

以下に、さまざまなヒープ データ構造の時間計算量^{[ 10 ]}を示します。略語am.は、与えられた計算量が償却済みであることを示し、そうでない場合は最悪の場合の計算量です。「 O ( f )」および「Θ ( f )」の意味については、ビッグ O 記法を参照してください。操作名は、最小ヒープを前提としています。

優先度キューのセマンティクスは、自然とソート方法を示唆します。ソート対象のすべての要素を優先度キューに挿入し、順番に取り出すと、ソートされた順序で取り出されます。これは、優先度キューによって提供される抽象化レイヤーを取り除くと、実際にはいくつかのソートアルゴリズムで使用されている手順です。このソート方法は、次のソートアルゴリズムと同等です。

ソートアルゴリズムは優先度キューを実装するためにも使用できます。具体的には、Thorupは次のように述べています。^{[ 26 ]}

優先度キューからソートへの一般的な決定論的線形空間削減を提示します。${\displaystyle n}$キーイン${\displaystyle S(n)}$キーごとの時間、そして優先度キューがサポートされdelete、insert${\displaystyle O(S(n))}$時間とfind-min一定時間において。

つまり、ソートできるソートアルゴリズムが存在する場合${\displaystyle O(S)}$キーごとの時間、${\displaystyle S}$は何らかの関数である${\displaystyle n}$ワードサイズ[ ^{27 ]}の場合、与えられた手順を使用して優先度キューを作成し、最も優先度の高い要素を取り出すことができます^。${\displaystyle O(1)}$時間、そして新しい要素の挿入（および要素の削除）は${\displaystyle O(S)}$時間。例えば、${\displaystyle O(n\log n)}$ソートアルゴリズムでは、優先度キューを作成できます。${\displaystyle O(1)}$引っ張って${\displaystyle O(\log n)}$挿入。

優先度キューイングは、ネットワークルータからの伝送回線の帯域幅など、限られたリソースを管理するために使用できます。帯域幅不足により送信トラフィックがキューイングされた場合、他のすべてのキューを停止して、到着したトラフィックを最優先キューから送信できます。これにより、優先度の高いトラフィック（VoIP接続のRTPストリームなどのリアルタイムトラフィック）が、キューが最大容量に達したために拒否される可能性が最小限に抑えられ、遅延が最小限に抑えられて転送されることが保証されます。最優先キューが空になったときに、他のすべてのトラフィックを処理できます。別の方法として、優先度の高いキューから不均衡に多くのトラフィックを送信する方法もあります。

ローカルエリアネットワーク向けの多くの最新プロトコルには、メディアアクセスコントロール（MAC）サブレイヤでの優先度キューの概念も含まれており、優先度の高いアプリケーション（ VoIPやIPTVなど）が、ベストエフォートサービスで提供される他のアプリケーションよりも低いレイテンシを経験できるようにします。例としては、IEEE 802.11e （サービス品質を提供するIEEE 802.11の修正版）やITU-T G.hn （既存の家庭用配線（電力線、電話線、同軸ケーブル）を使用した高速ローカルエリアネットワークの標準）などがあります。

通常、最優先キューからのトラフィックが使用できる帯域幅を制限するために、制限（ポリサー）が設定されます。これは、優先度の高いパケットが他のすべてのトラフィックを遮断してしまうのを防ぐためです。Cisco CallManagerなどの高レベル制御インスタンスは、設定された帯域幅制限を超える通話を抑制するようにプログラムできるため、この制限に達することは通常ありません。

優先度付きキューのもう一つの用途は、離散イベントシミュレーションにおけるイベントの管理です。イベントは、シミュレーション時間を優先度としてキューに追加されます。シミュレーションの実行は、キューの最上位を繰り返し取り出し、その中のイベントを実行することによって進められます。

関連項目：スケジューリング（コンピューティング）、待ち行列理論

グラフが隣接リストまたは行列の形式で格納されている場合、ダイクストラ法を実装する際に優先度キューを使用して最小値を効率的に抽出できますが、優先度キュー内の特定の頂点の優先度を効率的に変更できる機能も必要です。

代わりに、グラフをノードオブジェクトとして格納し、優先度とノードのペアをヒープに挿入する場合、訪問済みノードを追跡していれば、特定の頂点の優先度を変更する必要はありません。ノードが訪問されると、以前に低い優先度番号が関連付けられていた場合、そのノードはヒープからポップされて無視されます。

ハフマン符号化では、出現頻度が最も低い2つの木を繰り返し取得する必要がある。優先度付きキューは、この方法の一つである。

A*探索アルゴリズムのような最良優先探索アルゴリズムは、重み付きグラフの2つの頂点またはノード間の最短経路を、最も有望な経路から順に試行して見つけます。優先度キュー（フリンジとも呼ばれる）は、未探索の経路を追跡するために使用され、経路の全長の推定値（A*の場合は下限値）が最小の経路に最高の優先度が与えられます。メモリ制限により最良優先探索が実用的でない場合は、SMA*アルゴリズムのような派生アルゴリズムを使用できます。このアルゴリズムでは、優先度の低い項目を削除できるように、両端に優先度を持つキューが使用されます。

リアルタイム最適適応メッシュ（ROAM）アルゴリズムは、地形の動的に変化する三角形分割を計算します。このアルゴリズムは、より詳細な情報が必要な場所では三角形を分割し、より詳細な情報が必要ない場所では三角形を結合することで機能します。アルゴリズムは、地形内の各三角形に優先度を割り当てます。優先度は通常、その三角形を分割した場合の誤差の減少量に関連しています。アルゴリズムは、分割可能な三角形用と結合可能な三角形用の2つの優先度キューを使用します。各ステップでは、分割キューから優先度が最も高い三角形が分割されるか、結合キューから優先度が最も低い三角形が隣接する三角形と結合されます。

連結無向グラフの最小全域木を見つけるプリムのアルゴリズムで最小ヒープ優先度キューを使用すると、良好な実行時間を実現できます。この最小ヒープ優先度キューは、、、などの操作をサポートする最小ヒープデータ構造を使用します。[ 28 ^{]この実装}では、エッジの重みを使用して頂点の優先度を決定します。重みが小さいほど優先度が高く、重みが大きいほど優先度が低くなります。^{[ 29 ]}insertminimumextract-mindecrease-key

優先度キューが同時アクセスを許可する場合、複数のプロセスがその優先度キューに対して同時に操作を実行できます。しかし、これには2つの問題があります。まず、個々の操作の意味論の定義が明確ではなくなります。例えば、2つのプロセスが最も優先度の高い要素を抽出したい場合、同じ要素を取得すべきでしょうか、それとも異なる要素を取得すべきでしょうか？これは、優先度キューを使用するプログラムレベルでの並列処理を制限します。さらに、複数のプロセスが同じ要素にアクセスできるため、競合が発生します。

優先度キューへの同時アクセスは、同時読み出し、同時書き込み (CRCW) PRAM モデルで実装できます。以下では、優先度キューはスキップ リストとして実装されています。^{[ 30 ] [ 31 ]}さらに、スキップ リストをロックフリーにするために、アトミック同期プリミティブCASが使用されます。スキップ リストのノードは、一意のキー、優先度、各レベルの次のノードへのポインタの配列、およびマークで構成されます。マークは、ノードがプロセスによって削除されようとしているかどうかを示します。これにより、他のプロセスが削除に適切に対応できるようになります。deletedelete

• insert(e)まず、キーと優先度を持つ新しいノードが作成されます。さらに、ノードにはレベル数が割り当てられ、これがポインタ配列のサイズを決定します。次に、新しいノードを挿入する正しい位置を見つけるための検索が実行されます。検索は最初のノードと最上位レベルから開始されます。その後、正しい位置が見つかるまで、スキップリストが最下位レベルまで走査されます。検索中、各レベルで最後に走査されたノードが、そのレベルの新しいノードの親ノードとして保存されます。さらに、そのレベルの親ノードのポインタが指すノードが、そのレベルの新しいノードの後継ノードとして保存されます。その後、新しいノードの各レベルについて、親ノードのポインタが新しいノードに設定されます。最後に、新しいノードの各レベルのポインタが、対応する後継ノードに設定されます。
• extract-mindeleteまず、スキップリストを走査し、マークが設定されていないノードに到達します。delete次に、そのノードのマークをtrueに設定します。最後に、削除されたノードの親ノードへのポインタを更新します。

優先度キューへの同時アクセスが許可されている場合、2 つのプロセス間で競合が発生する可能性があります。たとえば、あるプロセスが新しいノードを挿入しようとしているときに、別のプロセスがそのノードの先行ノードを削除しようとしている場合、競合が発生します。^{[ 30 ]}新しいノードがスキップリストに追加されるものの、到達できなくなるリスクがあります。（図を参照）

この設定では、優先度キューの操作はバッチに一般化されます。${\textstyle k}$k_extract-min要素。たとえば、${\textstyle k}$優先度キューの最小要素を取得し、それらを返します。

共有メモリ環境では、並列優先度キューは並列二分探索木と結合ベースのツリーアルゴリズムを使用して容易に実装できます。特に、は、を持つ二分探索木上の分割k_extract-minに対応します。${\textstyle O(\log n)}$コストと、含まれる木を生成する${\textstyle k}$最小要素。元の優先度キューと挿入バッチの和集合k_insertによって適用できます。バッチが既にキーでソートされている場合、k_insert${\textstyle O(k\log(1+{\frac {n}{k}}))}$コスト。そうでない場合は、まずバッチをソートする必要があるため、コストは${\textstyle O(k\log(1+{\frac {n}{k}})+k\log k)=O(k\log n)}$優先度キューの他の操作も同様に適用できます。たとえば、k_decrease-key最初に を適用してdifferenceからを適用することで実行unionできます。これは、最初に要素を削除し、更新されたキーでそれらを再度挿入します。これらの操作はすべて高度に並列化されており、理論的および実践的な効率については、関連する研究論文を参照してください。^{[ 32 ] [ 33 ]}

このセクションの残りの部分では、分散メモリ上のキューベースのアルゴリズムについて説明します。各プロセッサは独自のローカルメモリとローカル（シーケンシャル）優先度キューを持つものとします。グローバル（並列）優先度キューの要素は、すべてのプロセッサに分散されます。

このk_insert操作では、要素を各プロセッサに均等にランダムに割り当て、各プロセッサはそれらの要素をローカルキューに挿入します。なお、単一の要素をキューに挿入することも可能です。この戦略を用いることで、グローバル最小要素は、各プロセッサのローカル最小要素の和集合に高い確率で含まれます。したがって、各プロセッサはグローバル優先度キューの代表的な部分を保持することになります。

このプロパティはk_extract-min、実行時に最小値として使用されます。${\textstyle m}$各ローカルキューの要素は削除され、結果セットに収集されます。結果セット内の要素は、元のプロセッサに関連付けられたままです。要素の数は${\textstyle m}$各ローカルキューから削除されるものは、${\textstyle k}$プロセッサの数${\textstyle p}$[ ^{34 ]並列} 選択により${\textstyle k}$結果セットの最小要素が決定されます。高い確率でこれらはグローバルです${\textstyle k}$最小要素。そうでない場合は、${\textstyle m}$要素は各ローカルキューから再び削除され、結果セットに追加されます。これはグローバルが${\textstyle k}$結果セットには最小の要素が含まれています。${\textstyle k}$要素が返される場合があります。結果セットのその他の要素はすべてローカルキューに挿入されます。実行時間k_extract-minは${\textstyle O({\frac {k}{p}}\log(n))}$、 どこ${\textstyle k=\Omega (p\cdot \log(p))}$そして${\textstyle n}$は優先度キューのサイズです。^{[ 34 ]}

優先度キューは、操作後に結果セットの残りの要素を直接ローカルキューに戻さないようにすることで、さらに効率化できますk_extract-min。これにより、結果セットとローカルキュー間で要素を何度も往復させる必要がなくなります。

一度に複数の要素を削除することで、かなりの高速化を実現できます。しかし、すべてのアルゴリズムがこの種の優先度キューを使用できるわけではありません。たとえば、ダイクストラ法は複数のノードを同時に処理することはできません。このアルゴリズムは、優先度キューから距離が最小のノードを取得し、そのすべての隣接ノードの新しい距離を計算します。${\textstyle k}$ノードでは、あるノードで作業すると、別のノードの距離が変わる可能性があります。${\textstyle k}$ノード。したがって、k要素演算を使用すると、ダイクストラ法のラベル設定特性が損なわれます。