私は最大ヒープの途中から特定の要素を削除するスカイライン問題を解決するアルゴリズムを実装しようとしています。私が現在やっているのはmaxheap.remove(index)ですが、私はheapify(maxheap)をフォローアップしなければなりません。私はあなたがそれを行うtreemapのような何かを使用することができますJavaで知っている。とにかく、それはO（n）時間かかる各別のメソッドを呼び出すよりも効率的にPythonで行うにはありますか？ヒープ内の特定の要素をPythonでヒーププロパティを失うことなく削除するには？
私は、各要素を無視するかどうかのフラグを持つデータ構造にする必要があります。あなたがヒップアップすると、それがフラグを立てた要素であれば、もう一度ポップします。これは非常に簡単で明白であり、ヒープが内部的にどのように動作するかについては何も知りません。たとえば、ヒープ内の要素が実際にどこにあるかを知る必要はありません。
このアプローチの欠点は、フラグが立てられた要素が時間とともに累積する傾向があることです。時にはそれらをフィルタリングしてからheapifyすることもできます。
このソリューションでは十分ではない場合は、Pythonでbtreeの実装を検索する必要があります。それはあなたがJavaで慣れているツリーマップのように振る舞います。
ヒープから任意の項目を削除するのは、その項目がヒープ内のどこにあるかを知っていれば、O（ログn）操作です。アルゴリズムは次のとおりです。
Move the last item in the heap to the position that contains the item to remove.
Decrement heap count.
If the item is smaller than its parent
bubble it up the heap
else
sift it down the heap
主な問題は、ヒープ内の項目の位置を見つけることです。あなたが指摘したように、もっと情報を保持しない限り、O（n）操作を実行します。
これを効率的に解決するには、アイテムキーを含む辞書を作成し、値はヒープ内のそのアイテムのインデックスです。ただし、辞書を維持する必要があります：あなたは、ヒープに項目を挿入するときは、変更するたびに、あなたが
その辞書を使用すると、ヒープ内のアイテムの位置にO（1）アクセス権があり、O（log n）で削除できます。
はい、インプリメンテーション方法に応じて、インデックスまたはポインタを持っている方が効率的です。
最大の 子で削除する必要があるインデックス/ポインタの番号を置き換え、子供がいないノードに到達するまで、子プロセスを再帰的に繰り返しますこれは簡単に削除できます。
このアルゴリズムの複雑さはO（log n）です。
あなたは、ヒープのどのような実装を参照してくださいか？ヒープ要素への明示的なアクセスを示す 'remove'演算子が含まれている場合、' change priority'を含むこともあります。 – MBo
@MBo Pythonでは明白な実装は標準ライブラリにあるheapqです。 – btilly