57

Pythonにはheapq、ヒープデータ構造を実装するモジュールがあり、いくつかの基本的な操作（push、pop）をサポートしています。

O（log n）のヒープからi番目の要素を削除するにはどうすればよいですか？heapq別のモジュールを使用することも可能ですか、それとも使用する必要がありますか？

ドキュメントの下部に例があります：http： //docs.python.org/library/heapq.html これは可能なアプローチを提案します-これは私が望むものではありません。単に削除済みとしてマークするのではなく、要素を削除したい。

4

2 に答える 2

76

ヒープからi番目の要素を非常に簡単に削除できます。

h[i] = h[-1]
h.pop()
heapq.heapify(h)

削除する要素を最後の要素に置き換え、最後の要素を削除してから、ヒープを再ヒープ化します。これはO（n）です。必要に応じて、O（log（n））で同じことを実行できますが、内部のheapify関数をいくつか呼び出す必要があります。ラースマンが指摘したように、 heapq.pyから独自のコードへの_siftup/_siftdown：

h[i] = h[-1]
h.pop()
if i < len(h):
    heapq._siftup(h, i)
    heapq._siftdown(h, 0, i)

いずれの場合も、最後の要素を参照するh[i] = h.pop()と失敗するため、実行できないことに注意してください。i特別な場合に最後の要素を削除する場合は、上書きとポップを組み合わせることができます。

ヒープの一般的なサイズによっては、heapify理論的には効率が低いときに呼び出すだけで、再利用するよりも高速になる場合があることに注意してください_siftup。/ _siftdown：少し内省すると、heapifyおそらくCで実装されているが、内部関数のC実装であることがわかります。公開されていません。パフォーマンスが重要な場合は、一般的なデータに対してタイミングテストを実行して、どれが最適かを確認することを検討してください。あなたが本当に大きなヒープを持っていない限り、Oは最も重要な要素ではないかもしれません。

編集：_siftdown誰かがこの回答を編集して、次のようなコメントを付けてへの呼び出しを削除しようとしました。

_siftdownは必要ありません。新しいh[i]は、古いh [i]の子の中で最小であることが保証されています。これは、古いh [i]の親（新しいh [i]の親）よりもまだ大きいです。_siftdownはノーオペレーションになります。コメントを追加するのに十分な担当者がいないため、編集する必要があります。

彼らがこのコメントで見逃したのは、それh[-1]はまったく子供ではないかもしれないということh[i]です。に挿入された新しい値h[i]は、ヒープの完全に異なるブランチから取得される可能性があるため、どちらの方向にもふるいにかける必要がある場合があります。

sort()また、ヒープを復元するために使用しない理由を尋ねるコメントにも、両方ともO（log n）操作で_siftupあり_siftdown、heapifyの呼び出しはO（n）です。呼び出しsort()はO（n log n）操作です。sortの呼び出しが十分に高速になる可能性は十分にありますが、ヒープが大きい場合は不要なオーバーヘッドになります。

@SethBruderによって指摘された問題を回避するために編集されました。iend要素を参照する場合、_siftup()呼び出しは失敗しますが、その場合、ヒープの終わりから要素をポップしても、ヒープ不変条件は壊れません。

于 2012-04-15T15:35:11.330 に答える
18

（a）怠惰な削除を望まない理由を検討してください。多くの場合、これは適切なソリューションです。

（b）ヒープはリストです。他のリストと同じように、インデックスで要素を削除できますが、ヒープ不変条件を満たさなくなるため、要素を再ヒープ化する必要があります。

于 2012-04-15T14:03:01.753 に答える