これが私のシナリオです。線形時間の分や操作に頼ることなく、A *（Pythonで）を実装したいと思います。最小重量のアイテムを効率的に取得できるようにするには、ヒープが必要です。
私の即時の応答は'簡単でした！heapqを使用します！」それから私は、人生が私たちが望むほど単純であることはめったにないことを発見しました。この戦略は、A*の重要なポイントの1つにとって最適ではないことがわかりました。子供を考えるとき、私は時々、すでにヒープ上にある子供たちのスコアを更新する必要があります。
A *の記憶が少しなくなった人にとって、その要点は、要素を取得し、その重みを変更し、変更を反映するようにヒープを変更することです。これらはすべて劣線形時間で行われます。
助言がありますか？
複雑にするために、二項式またはフィボナッチヒープを試してみてください。Pythonには両方の実装がありますが、本番グレードのライブラリにはないようです。ただし、実際には、バイナリヒープまたはd-aryヒープの方が高速に動作する可能性があります。このheapqページには、更新の方法が記載されています（ヒープに挿入するアイテムへの参照を保持し、無効としてマークしてから、新しいバージョンを挿入します）。ただし、更新後にヒーププロパティを維持するためのより高速なアルゴリズムがあります。高速更新に使用するアルゴリズムについては、 http：//en.wikipedia.org/wiki/D-ary_heapを参照してください。ただし、それらの配列の上に独自のヒープを実装する必要があるでしょう。
確かに、ヒープは機能せず、非常に機能的でheapqもQueue.PriorityQueueありません。A：ブログに暴言を書くか、B：自分で暴言を実装するのに、おそらくほぼ同じ時間がかかります。
実際にヒープを検索できないという正確な理由から、私は常に独自のバージョンのヒープ型を実装することになりますが、すべての効率的なメソッドは入力として「要素へのポインター」を必要とします。
通常、ヒープは、アイテムの非構造化コンテナと、アイテムへのポインタ（またはインデク）のヒープの組み合わせとして実装します。アイテム内のヒープ位置へのポインターを保持している場合は、すぐに双方向のリンクがあります。a）ヒープ要素が与えられた場合（extractMinによって返される、または比較中に）：ポインターを逆参照すると、アイテム。b）アイテムが与えられた場合（たとえば、グラフアルゴリズムの隣接リストを介して）：必要な更新関数へのポインターを渡します。
もちろん、これによりスペースのオーバーヘッドが発生します（アイテムごとに2つの追加のポインター/整数）が、ヒープの再構築が非常に安価になり（アイテム全体を交換する代わりにいくつかのポインターを交換する）、その結果、衛星データを追加するのが簡単になります。あなたのアイテム。