プリムのアルゴリズムのヒープ内の要素の優先順位を更新するにはどうすればいいですか？

Question

私はプリムのアルゴリズムを研究しています。コード内には、カット内の次の頂点がMSTに属する頂点のセットに来る部分があります。これを実行している間に、出発する頂点に隣接する他のセットのすべての頂点も更新する必要があります。これはCLRSからのスナップショットです：

興味深い部分は、ラインなしです。 11.ここではヒープを使用しているため、最小要素、right（heap[0]）のみにアクセスできますか？では、最小値ではないにもかかわらずヒープから頂点を検索して更新するにはどうすればよいのですか？

Answer 1

reduce-keyという操作をサポートするプライオリティキューを構築することができます。このキューは、プライオリティキュー内の既存オブジェクトのプライオリティを受け取り、それを下げます。既存のライブラリに同梱されているほとんどのバージョンの優先順位キューは、この操作をサポートしていませんが、いくつかの方法で構築することができます。

たとえば、バイナリヒープを指定すると、バイナリヒープの要素からその位置にマップする補助データ構造を維持できます。その後、スワップが実行されるたびに、この補助データ構造が更新されるように、バイナリヒープ実装を更新します。次に、reduce-keyを実装するには、テーブルにアクセスし、バイナリヒープ内のノードの位置を見つけて、バブルアップステップを続行します。

2項ヒープまたはフィボナッチヒープのような他のポインタベースのヒープは、この操作を明示的にサポートしています（フィボナッチヒープは、そのために特別に設計されています）。通常、オブジェクトからヒープ内で占有するノードまでの補助マップがあり、ポインタを再配線してヒープ内のノードを移動させることができます。

希望すると便利です。

Answer 2

ポインタは、あなたが（擬似コードC++を使用して）このようなものを持って効率的な複合データ構造に

を有効にします。

class Node 
    bool visited 
    double key 
    Node* pi 
    vector<pair<Node*, double>> adjacent //adjacent nodes and edge weights 
    //and extra fields needed for PriorityQueue data structure 
    // - a clean way to do this is to use CRTP for defining the base 
    // PriorityQueue node class, then inherit your graph node from that 

class Graph 
    vector<Node*> vertices 

CRTP：http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern

アルゴリズムにおけるプライオリティキューQはの項目が含まれていますNode*と入力してください。ExtractMinには、の最小のNode*が表示されます。。あなたがu = ExtractMin(Q)を得るとき、あなたはNode*を持っている、ので、あなたが任意の線形検索を行う必要はありません

理由があります。だからu->adjacentはvをG.Adj[u]に、w(u,v)をの隣接ノードあたりに設定します。プライオリティキューノード（はv）へのポインタvがあるので、プライオリティキューの位置は、（優先度キューの実装が最も多い）のの対数時間で更新できます。

以下に使用されるDecreaseKey(Q, v)関数は、フィボナナシヒープとペアリングヒープ（償却）の対数複雑さを持っています。

• ペアリングヒープ：自分をコーディングするhttp://en.wikipedia.org/wiki/Pairing_heap
  • あまりにもハードではない - ウィキペディアは、ソースコード
• フィボナッチヒープのほとんどを持っていますhttp://en.wikipedia.org/wiki/Fibonacci_heap

のためのより多くの、具体的な擬似コードアルゴリズム

MstPrim(Graph* G) 
    for each u in G->vertices 
     u->visited = false 
     u->key = infinity 
     u->pi = NULL 
    Q = PriorityQueue(G->vertices) 
    while Q not empty 
     u = ExtractMin(Q) 
     u->visited = true 
     for each (v, w) in u->adjacent 
      if not v->visited and w < v->key 
       v->pi = u 
       v->key = w 
       DecreasedKey(Q, v) //O(log n)