プリムのアルゴリズムを勉強しています。コード内に、カットを横切る次の頂点が に属する頂点のセットになる部分がありますMST。それをしている間、「出発する頂点に隣接する他のセットのすべての頂点を更新する」必要もあります。これは からのスナップショットですCLRS:
興味深い部分は行番号にあります。11. でも、ここではヒープを使っているので、最小限の要素しかアクセスできませんよね ( heap[0])? では、ヒープから頂点を検索して更新するにはどうすればよいでしょうか? 頂点が最小の頂点ではなく、線形検索を除いて頂点がどこにあるかを知っている場合でも、どうすればよいでしょうか?
プライオリティ キュー内の既存のオブジェクトのプライオリティを取得して下げる、recrease -keyと呼ばれる操作をサポートするプライオリティ キューを構築することができます。既存のライブラリに同梱されているプライオリティ キューのほとんどのバージョンは、この操作をサポートしていませんが、いくつかの方法で構築できます。
たとえば、バイナリ ヒープが与えられた場合、要素からバイナリ ヒープ内の位置にマップする補助データ構造を維持できます。次に、バイナリ ヒープの実装を更新して、スワップが実行されるたびにこの補助データ構造が更新されるようにします。次に、キーの減少を実装するために、テーブルにアクセスし、バイナリ ヒープ内のノードの位置を見つけてから、バブルアップ ステップを続行します。
二項ヒープやフィボナッチ ヒープなどの他のポインター ベースのヒープは、この操作を明示的にサポートします (フィボナッチ ヒープはこの操作のために特別に設計されました)。通常、オブジェクトから、オブジェクトがヒープ内で占めるノードへの補助マップがあり、ポインターを再配線してノードをヒープ内で移動できます。
お役に立てれば！