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