優先キュー

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータサイエンスでは優先度付きキューは、通常のキューまたはスタックデータ構造に似た抽象データ型であり、各要素にはさらに「優先度」が関連付けられています。優先度キューでは、優先度の高い要素が優先度の低い要素の前に提供されます。一部の実装では、2つの要素の優先度が同じである場合、それらはキューに入れられた順序に従って提供されます。他の実装では、同じ優先順位を持つ要素の順序は未定義のままです。

コーダーはヒープを使用して優先キューを実装することがよくありますが、概念的にはヒープとは異なります。優先キューは、「リスト」や「マップ」のような概念です。リストをリンクリストまたは配列で実装できるのと同じように、優先度付きキューはヒープまたは順序付けされていない配列などの他のさまざまな方法で実装できます。

操作

優先キューは、少なくとも次の操作をサポートする必要があります。

  • is_empty:キューに要素がないかどうかを確認します。
  • insert_with_priority関連付けられた優先度を持つ要素キューに追加します。
  • pull_highest_priority_element :最高の優先度を持つ要素をキューから削除し、それを返します。
    これは、「pop_element(Off)」、「get_maximum_element」、または「get_front(most)_element」とも呼ばれます。
    一部の規則では、優先度の順序が逆になり、値が小さいほど優先度が高いと見なされるため、これは「get_minimum_element 」とも呼ばれ、文献では「 get-min 」と呼ばれることがよくあります。
    代わりに、これを個別の「peek_at_highest_priority_element」関数と「delete_element」関数として指定することできます。これらの関数を組み合わせて「pull_highest_priority_element」を生成できます。

さらに、最も優先度の高い要素を返すがキューを変更しないpeek(このコンテキストではfind-maxまたはfind-minと呼ばれることが多い)は非常に頻繁に実装され、ほとんどの場合O(1)時間で実行されます。この操作とそのO(1)パフォーマンスは、優先キューの多くのアプリケーションにとって重要です。

より高度な実装では、 pull_lowest_priority_element、最初のいくつかの最高または最低の優先度要素の検査、キューのクリア、キューのサブセットのクリア、バッチ挿入の実行、2つ以上のキューの1つへのマージ、優先度の増分など、より複雑な操作をサポートできます。任意の要素などの

スタックキューは、優先キューとは異なります。優先キューでは、順序は本質的です。挿入される値によって異なります。スタックまたはキューでは、順序は外部的です。値が挿入される順序によって異なります。振る舞いサブタイピングに関して、キューは優先キューのサブタイプではなく、優先キューはキューのサブタイプではありません。一方を他方に置き換えることはできません。また、継承階層で一方を他方のサブタイプにすることもできません。

実装

素朴な実装

優先キューを実装するには、さまざまな単純な、通常は非効率的な方法があります。それらは、優先キューが何であるかを理解するのに役立つアナロジーを提供します。

たとえば、すべての要素をソートされていないリストに保持できます(O(1)挿入時間)。最も優先度の高い要素が要求されるたびに、すべての要素を検索して、最も優先度の高い要素を探します。On)プル時間)、

挿入(ノード)
{{
  list.append(node)
}
プル()
{{
  最高=list.get_first_element()
  リスト内のforeachノード
  {{
     最高の場合.priority<node.priority
     {{
         最高=ノード
     }
  }
  list.remove(最高)
  最高のリターン
}

別のケースでは、すべての要素を優先度ソートリスト(O(n)挿入ソート時間)に保持できます。最も優先度の高い要素が要求されるたびに、リストの最初の要素を返すことができます。O(1)プル時間)

挿入(ノード)
{{
  リスト内のforeach(インデックス、要素)
  {{
    node.priority<element.priorityの場合
    {{
       list.insert_at_index(node、index)
    }
  }
}
プル()
{{
    最高=list.get_at_index(list.length-1)
    list.remove(最高)
    最高のリターン
}

通常の実装

パフォーマンスを向上させるために、優先度付きキューは通常、ヒープ基づいており、挿入と削除にO(log n )のパフォーマンスを提供し、 On )はn個の要素のセットから最初にヒープを構築します。ペアリングヒープフィボナッチヒープなどの基本的なヒープデータ構造のバリエーションは、一部の操作に対してより適切な境界を提供できます。[1]

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

計算の複雑さの観点から、優先度付きキューは並べ替えアルゴリズムと一致しています。以下の優先度付きキューと並べ替えアルゴリズムの同等性に関するセクションでは、効率的な並べ替えアルゴリズムによって効率的な優先度付きキューを作成する方法について説明します。

特殊なヒープ

特定のタイプのキー、具体的には整数キーに対して、追加の操作を提供するか、ヒープベースの実装よりも優れたパフォーマンスを発揮する、いくつかの特殊なヒープ データ構造があります。可能なキーのセットが{1、2、...、C}であると仮定します。

  • insertfind-minextract-minのみが必要な場合、および整数の優先順位の場合、バケットキューは、 C リンクリストの配列とポインタトップ(最初はC)として構築できますキーkを使用してアイテムを挿入すると、アイテムがk番目に追加され、top←min(top、kが一定時間で更新されます。Extract-minは、インデックスtopを持つリストから1つのアイテムを削除して返し、必要に応じて、空でないリストを再度指すまでtopをインクリメントします。これはOを取りますC最悪の場合の時間。これらのキューは、グラフの頂点を次数で並べ替えるのに役立ちます。[2] :374 
  • van Emde Boasツリーは、 O (log log C)時間で最小最大挿入削除検索extract-minextract-max先行および後続操作をサポートしますが、約Olog log C)の小さなキューのスペースコストがあります。2 m / 2)、ここでmは優先度値のビット数です。[3]ハッシュを使用すると、スペースを大幅に削減できます。
  • FredmanWillardによるFusionツリーは、 O(1)時間最小操作を実装し時間。しかし、著者は、「私たちのアルゴリズムは理論的な関心しか持たない。実行時間に関係する一定の要因が実用性を妨げる」と述べている。[4]

「extract-min」操作ごとに多くの「 peek 」操作を実行するアプリケーションの場合、挿入と削除のたびに最も優先度の高い要素をキャッシュすることで、すべてのツリーとヒープの実装でピークアクションの時間計算量をO (1)に減らすことができます。挿入の場合、新しく挿入された要素は以前にキャッシュされた最小要素とのみ比較されるため、これにより最大で一定のコストが追加されます。削除の場合、これはせいぜい追加の「ピーク」コストを追加します。これは通常、削除コストよりも安いため、全体的な時間計算量に大きな影響はありません。

モノトーン優先キューは、以前に抽出されたアイテムよりも優先度が低い(最小ヒープの場合)アイテムが挿入されない場合に最適化された特殊なキューです。この制限は、優先キューのいくつかの実用的なアプリケーションによって満たされます。

実行時間の概要

さまざまなヒープデータ構造の時間計算量[5]を次に示します。関数名は最小ヒープを想定しています。「 Of)」および「Θf )」の意味については、 BigO表記を参照してください

手術 検索-分 削除分 入れる 減少キー メルド
バイナリ[5] Θ(1) Θ(log  n O(log  n O(log  n Θn
左翼 Θ(1) Θ(log n Θ(log n O(log n Θ(log n
二項[5] [6] Θ(1) Θ(log n Θ(1)[a] Θ(log n O(log  n[b]
フィボナッチ[5] [7] Θ(1) O(log  n[a] Θ(1) Θ(1)[a] Θ(1)
ペアリング[8] Θ(1) O(log n[a] Θ(1) o(log  n[a] [c] Θ(1)
ブロダル[11] [d] Θ(1) O(log  n Θ(1) Θ(1) Θ(1)
ランクペアリング[13] Θ(1) O(log n[a] Θ(1) Θ(1)[a] Θ(1)
厳格なフィボナッチ[14] Θ(1) O(log n Θ(1) Θ(1) Θ(1)
2〜3ヒープ[15] O(log n O(log n[a] O(log n[a] Θ(1)
  1. ^ a b c d e f ghi 償却時間
  2. ^ nは、大きい方のヒープのサイズです。
  3. ^ 下界[9]上界と下界[10]
  4. ^ BrodalとOkasakiは、サポートされていないdecrease-keyを除いて、同じ境界を持つ永続的なバリアントについて後で説明します。n個の要素を持つヒープは、 O n )でボトムアップで構築できます[12]

優先度付きキューと並べ替えアルゴリズムの同等性

優先キューを使用した並べ替え

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

名前 優先キューの実装 一番 平均 最悪
ヒープソート ヒープ
Smoothsort レオナルドヒープ
選択ソート 順序付けられていない配列
挿入ソート 順序付き配列
ツリーソート 自己平衡二分探索木

並べ替えアルゴリズムを使用して優先キューを作成する

ソートアルゴリズムを使用して、優先キューを実装することもできます。具体的には、トルップは次のように述べています。[16]

優先キューからソートへの一般的な決定論的線形スペース削減を提示します。これは、キーごとにSn)時間で最大n個のキーをソートできる場合OSn))での削除挿入をサポートする優先キューがあることを意味します。時間と一定時間 のfind-min 。

つまり、キーごとにOS )時間で並べ替えることができる並べ替えアルゴリズムがあり、 Sはnワードサイズ関数である場合[17]、指定された手順を使用して優先キューを作成できます。最も優先度の高い要素はO(1)時間であり、新しい要素の挿入(および要素の削除)はOS)時間です。たとえば、On  log  n)ソートアルゴリズムがある場合、O(1)プルとO(n log  n)挿入で優先キューを作成できます。

ライブラリ

優先キューは、「コンテナデータ構造」と見なされることがよくあります

標準テンプレートライブラリ(STL)およびC ++ 1998標準では、STLコンテナアダプタクラステンプレートの1つとしてstd::priority_queueが指定されています。ただし、同じ優先度を持つ2つの要素をどのように提供するかは指定されておらず、実際、一般的な実装では、キュー内の順序に従ってそれらを返すことはありません。max-priority-queueを実装し、3つのパラメーターがあります。関数オブジェクトなどの並べ替え用の比較オブジェクト(指定されていない場合はデフォルトでless <T>)、データ構造を格納するための基になるコンテナー(デフォルトでstd :: vector) <T>)、およびシーケンスの最初と最後への2つのイテレータ。実際のSTLコンテナとは異なり、反復は許可されません その要素の(抽象データ型の定義に厳密に準拠しています)。STLには、別のランダムアクセスコンテナをバイナリ最大ヒープとして操作するためのユーティリティ関数もあります。Boostライブラリには、ライブラリヒープにも実装があります。

Pythonのheapqモジュールは、リストの上にバイナリ最小ヒープを実装します。

JavaのライブラリにはPriorityQueue、min-priority-queueを実装するクラスが含まれています。

.NETのライブラリにはPriorityQueueクラスが含まれています。このクラスは、配列に裏打ちされた4分の1の最小ヒープを実装します。

Scalaのライブラリには、max-priority-queueを実装する PriorityQueueクラスが含まれています。

Goのライブラリには、互換性のあるデータ構造の上に最小ヒープを実装する コンテナ/ヒープモジュールが含まれています。

標準のPHPLibrary拡張機能には、クラスSplPriorityQueueが含まれています。

AppleのCoreFoundationフレームワークには、最小ヒープを実装するCFBinaryHeap構造含まれています。

アプリケーション

帯域幅管理

プライオリティキューイングは、ネットワークルーターからの伝送ラインの帯域幅などの限られたリソースを管理するために使用できます帯域幅が不十分なために発信トラフィックがキューに入れられた場合、他のすべてのキューを停止して、到着時に最も優先度の高いキューからトラフィックを送信できます。これにより、優先順位の高いトラフィック(VoIP接続のRTPストリームなどのリアルタイムトラフィックなど)が最小の遅延で転送され、キューが最大容量に達したために拒否される可能性が最小になります。他のすべてのトラフィックは、最も優先度の高いキューが空のときに処理できます。使用される別のアプローチは、優先度の高いキューから不釣り合いに多くのトラフィックを送信することです。

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

通常、制限(ポリサー)は、優先度の高いパケットが他のすべてのトラフィックを窒息させないようにするために、優先度の最も高いキューからのトラフィックが使用できる帯域幅を制限するように設定されます。通常、 Cisco Callmanagerなどの高レベルの制御インスタンスが原因でこの制限に達することはありません。CiscoCallmanagerは、プログラムされた帯域幅制限を超えるコールを禁止するようにプログラムできます。

離散イベントシミュレーション

優先キューのもう1つの用途は、離散イベントシミュレーションでイベントを管理することです。イベントは、シミュレーション時間を優先してキューに追加されます。シミュレーションの実行は、キューの先頭を繰り返しプルし、その上でイベントを実行することによって進行します。

参照スケジューリング(コンピューティング)待ち行列理論

ダイクストラのアルゴリズム

グラフが隣接リストまたはマトリックスの形式で保存されている場合、優先キューを使用して、ダイクストラのアルゴリズムを実装するときに最小値を効率的に抽出できますが、優先キュー内の特定の頂点の優先度を効率的に変更する機能も必要です。

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

ハフマン符号化

ハフマン符号化では、2つの最低頻度ツリーを繰り返し取得する必要があります。優先キューは、これを行う1つの方法です

最良優先探索アルゴリズム

A *検索アルゴリズムのような最良優先探索アルゴリズムは、重み付きグラフの2つの頂点またはノード間の最短経路を見つけ、最も有望なルートを最初に試します。優先キュー(フリンジとも呼ばれます)は、未踏のルートを追跡するために使用されます。総経路長の推定値(A *の場合は下限)が最も小さいものが最優先されます。メモリの制限により最良優先探索が実用的でない場合は、代わりにSMA *アルゴリズムなどのバリアントを使用して、優先度の低いアイテムを削除できるようにする 両端優先キューを使用できます。

ROAM三角測量アルゴリズム

Real-time Optimally Adapting Meshes(ROAM)アルゴリズムは、動的に変化する地形の三角形分割を計算します。これは、より詳細な情報が必要な場所で三角形を分割し、詳細度が必要でない場所で三角形をマージすることで機能します。アルゴリズムは、地形内の各三角形に優先順位を割り当てます。これは通常、その三角形が分割される場合のエラーの減少に関連しています。このアルゴリズムは、2つの優先度キューを使用します。1つは分割可能な三角形用で、もう1つはマージ可能な三角形用です。各ステップで、優先度が最も高い分割キューの三角形が分割されるか、優先度が最も低いマージキューの三角形が隣接するものとマージされます。

最小全域木のためのプリムのアルゴリズム

プリムのアルゴリズム最小ヒープ優先度キューを使用して、接続され無向グラフの最小スパニングツリーを見つけると、良好な実行時間を達成できます。この最小ヒープ優先キューは、挿入最小抽出-最小減少キーなどの操作をサポートする最小ヒープデータ構造を使用します。[18]この実装では、エッジの重みを使用して頂点の優先度を決定します重みを低くすると、優先度が高くなり、重みが高くなると、優先度が低くなります。[19]

並列優先キュー

並列化を使用して優先キューを高速化できますが、優先キューインターフェイスにいくつかの変更を加える必要があります。このような変更の理由は、通常、順次更新にはまたコストがかかり、そのような操作を並列化するための実際的な利益はありません。考えられる変更の1つは、同じプライオリティキューへの複数のプロセッサの同時アクセスを許可することです。2番目に考えられる変更は、で機能するバッチ操作を許可することです。1つの要素ではなく、要素。たとえば、extractMinは最初のを削除します優先度が最も高い要素。

同時並列アクセス

優先キューで同時アクセスが許可されている場合、複数のプロセスがその優先キューで同時に操作を実行できます。ただし、これには2つの問題があります。まず第一に、個々の操作のセマンティクスの定義はもはや明白ではありません。たとえば、2つのプロセスが最も優先度の高い要素を抽出する場合、同じ要素を取得する必要がありますか、それとも異なる要素を取得する必要がありますか?これにより、優先キューを使用するプログラムのレベルでの並列処理が制限されます。さらに、複数のプロセスが同じ要素にアクセスできるため、これは競合につながります。

ノード3が挿入され、ノード2のポインターがノード3に設定されます。その直後に、ノード2が削除され、ノード1のポインターがノード4に設定されます。これでノード3に到達できなくなります。

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

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

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

K要素演算

この設定では、優先キューの操作は次のバッチに一般化されます。要素。たとえば、k_extract-min優先キューの最小要素であり、それらを返します。

共有メモリ設定では、並列二分探索木結合ベースのツリーアルゴリズムを使用して、並列優先度キューを簡単に実装できます特に、k_extract-minは、次のような二分探索木の分割に対応します。コストとを含むツリーを生成します最小の要素。 k_insertは、元の優先度キューと挿入のバッチの和集合によって適用できます。バッチがすでにキーでソートされている場合、k_insertには費用。それ以外の場合は、最初にバッチを並べ替える必要があるため、コストは次のようになります。優先キューの他の操作も同様に適用できます。たとえば、k_decrease-keyは、最初に差分を適用し、次にunionを適用することで実行できます。これにより、最初に要素が削除され、次に更新されたキーで要素が挿入されます。これらの操作はすべて高度に並行しており、理論的および実用的な効率は関連する研究論文に記載されています。[22] [23]

このセクションの残りの部分では、分散メモリでのキューベースのアルゴリズムについて説明します。各プロセッサには、独自のローカルメモリとローカル(シーケンシャル)優先キューがあると想定しています。グローバル(パラレル)プライオリティキューの要素は、すべてのプロセッサに分散されています。

k_extract-minは、3つのプロセッサを備えた優先キューで実行されます。緑の要素が返され、優先キューから削除されます。

k_insert操作は、要素をローカルキューに挿入するプロセッサに均一にランダムに要素を割り当てます単一の要素を引き続きキューに挿入できることに注意してください。この戦略を使用すると、グローバルな最小要素は、すべてのプロセッサのローカルな最小要素の結合に高い確率で含まれます。したがって、各プロセッサはグローバルプライオリティキューの代表的な部分を保持します。

このプロパティは、k_extract-minが実行されるときに、最小のものとして使用されます各ローカルキューの要素が削除され、結果セットに収集されます。結果セットの要素は、元のプロセッサに関連付けられたままです。要素の数各ローカルキューから削除されるのは、とプロセッサの数[24] 並列選択により、結果セットの最小要素が決定されます。高い確率でこれらはグローバルです最小の要素。そうでない場合は、要素は再び各ローカルキューから削除され、結果セットに入れられます。これは、グローバルになるまで行われます最小の要素が結果セットに含まれます。今これら要素を返すことができます。結果セットの他のすべての要素は、ローカルキューに挿入されます。k_extract-minの実行時間は予想されます、 どこは優先キューのサイズです。[24]

k_extract-min操作の後で、結果セットの残りの要素をローカルキューに直接戻さないことで、優先キューをさらに改善できます。これにより、結果セットとローカルキューの間で要素を前後に移動する必要がなくなります。

一度にいくつかの要素を削除することにより、かなりのスピードアップを達成することができます。ただし、すべてのアルゴリズムがこの種の優先キューを使用できるわけではありません。たとえば、ダイクストラのアルゴリズムは、一度に複数のノードで機能することはできません。アルゴリズムは、優先キューからの距離が最小のノードを取得し、そのすべての隣接ノードの新しい距離を計算します。テイクアウトするならノード、あるノードで作業すると、別のノードの距離が変わる可能性がありますノード。したがって、k要素演算を使用すると、ダイクストラのアルゴリズムのラベル設定プロパティが破壊されます。

も参照してください

参照

  1. ^ コルメン、トーマスH .; レイザーソン、チャールズE .; リベスト、ロナルドL .; スタイン、クリフォード(2001)[1990]。「第20章:フィボナッチヒープ」。アルゴリズム入門(第2版)。MITPressとMcGraw-Hill。pp。476–497。ISBN 0-262-03293-7第3版、p。518。
  2. ^ スキーナ、スティーブン(2010)。アルゴリズム設計マニュアル(第2版)。シュプリンガーサイエンス+ビジネスメディアISBN 978-1-849-96720-4
  3. ^ P. van Emde Boas 対数時間未満で森林の秩序を維持する。コンピュータサイエンスの基礎に関する第16回年次シンポジウムの議事録、 75〜84ページ。IEEE Computer Society、1975年。
  4. ^ マイケルL.フレッドマンとダンE.ウィラード。融合ツリーとの情報理論的限界を超えています。Journal of Computer and System Sciences、48(3):533-551、1994
  5. ^ a b c d コルメン、トーマスH .; レイザーソン、チャールズE .; リベスト、ロナルドL.(1990)。アルゴリズム入門(第1版)。MITPressとMcGraw-Hill。ISBN 0-262-03141-8
  6. ^ 「二項ヒープ|BrilliantMath&ScienceWiki」brilliant.org 2019年9月30日取得
  7. ^ フレッドマン、マイケルローレンス; タージャン、ロバートE.(1987年7月)。「フィボナッチヒープと改善されたネットワーク最適化アルゴリズムでのそれらの使用」(PDF)Journal of the Association forComputingMachinery34(3):596–615。CiteSeerX10.1.1.309.8927_ 土井10.1145/28869.28874  
  8. ^ Iacono、John(2000)、「ペアリングヒープの上限の改善」、Proc。アルゴリズム理論に関する第7回スカンジナビアワークショップ(PDF)、コンピュータサイエンスのレクチャーノート、vol。1851、Springer-Verlag、pp。63–77、arXiv1110.4428CiteSeerX 10.1.1.748.7812doi10.1007 / 3-540-44985-X_5ISBN   3-540-67690-2
  9. ^ フレッドマン、マイケルローレンス(1999年7月)。「ペアリングヒープと関連データ構造の効率について」(PDF)Journal of the Association forComputingMachinery46(4):473–501。土井10.1145/320211.320214
  10. ^ ペティー、セス(2005)。ペアリングヒープの最終分析に向けて(PDF)FOCS'05コンピュータサイエンスの基礎に関する第46回IEEEシンポジウムの議事録。pp。174–183。CiteSeerX10.1.1.549.471_ 土井10.1109/SFCS.2005.75ISBN   0-7695-2468-0
  11. ^ Brodal、Gerth S.(1996)、「最悪の場合の効率的な優先度付きキュー」(PDF)Proc。離散アルゴリズムに関する第7回ACM-SIAMシンポジウム、 52〜58ページ
  12. ^ グッドリッチ、マイケルT .; タマシア、ロベルト(2004)。「7.3.6。ボトムアップヒープ構造」。Javaのデータ構造とアルゴリズム(第3版)。pp。338–341。ISBN 0-471-46983-1
  13. ^ Haeupler、Bernhard; セン、シッダールタ; Tarjan、Robert E.(2011年11月)。「ランクペアリングヒープ」(PDF)SIAMJ.コンピューティング40(6):1463–1485。土井10.1137/100785351
  14. ^ Brodal、GerthStølting ; Lagogiannis、ジョージ; Tarjan、Robert E.(2012)。厳密なフィボナッチヒープ(PDF)コンピューティング理論に関する第44回シンポジウムの議事録-STOC'12。pp。1177–1184。CiteSeerX10.1.1.233.1740_ 土井10.1145/2213977.2214082ISBN   978-1-4503-1245-5
  15. ^ 高岡忠夫(1999)、2–3ヒープの理論(PDF)、p。12
  16. ^ Thorup、ミッケル(2007)。「優先キューとソートの同等性」。ACMのジャーナル54(6):28. doi10.1145/1314690.1314692S2CID11494634_ 
  17. ^ 「アーカイブされたコピー」(PDF)2011年7月20日のオリジナルからアーカイブ(PDF)2011年2月10日取得 {{cite web}}:CS1 maint:タイトルとしてアーカイブされたコピー(リンク
  18. ^ コルメン、トーマスH .; レイザーソン、チャールズE .; リベスト、ロナルドL .; スタイン、クリフォード(2009)[1990]。アルゴリズム入門(第3版)。MITPressとMcGraw-Hill。ISBN 0-262-03384-4
  19. ^ 「プリムのアルゴリズム」オタクのためのオタク。2014年9月9日にオリジナルからアーカイブされました2014年9月12日取得
  20. ^ a b Sundell、Håkan; Tsigas、Philippas(2005)。「マルチスレッドシステム用の高速でロックフリーの同時優先キュー」Journal of Parallel andDistributedComputing65(5):609–627。土井10.1109/IPDPS.2003.1213189S2CID20995116_ 
  21. ^ Lindén、Jonsson(2013)、「最小限のメモリ競合を伴うスキップリストベースの同時優先度キュー」テクニカルレポート2018-003(ドイツ語)
  22. ^ Blelloch、Guy E .; フェリゾビッチ、ダニエル; Sun、Yihan(2016)、「並列順序集合に参加するだけ」、並列アルゴリズムとアーキテクチャに関するシンポジウム、Proc。第28回ACM症状の。Parallel Algorithms and Architectures(SPAA 2016)、ACM、pp。253–264、arXiv1602.02120doi10.1145 / 2935764.2935768ISBN 978-1-4503-4210-0S2CID  2897793
  23. ^ Blelloch、Guy E .; フェリゾビッチ、ダニエル; Sun、Yihan(2018)、「PAM:並列拡張マップ」、第23回ACM SIGPLANシンポジウムの議事録、並列プログラミングの原則と実践、ACM、290〜304ページ
  24. ^ a b サンダース、ピーター; メールホルン、カート; ディーツフェルビンガー、マーティン; デメンティエフ、ローマ(2019)。シーケンシャルおよび並列アルゴリズムとデータ構造-基本ツールボックススプリンガーインターナショナルパブリッシング。pp。226–229。土井10.1007/978-3-030-25209-0ISBN 978-3-030-25208-3S2CID201692657 _

さらに読む

外部リンク