python - 1 から N までのラベルが付けられたリスト L と、考慮対象からランダムな要素を「削除」するプロセスが与えられた場合、どうすれば min(L) を効率的に追跡できますか?

Question

質問はほとんどタイトルにありますが、リストLがあるとします

L = [1,2,3,4,5]

ここで min(L) = 1 です。次に、4 を削除します。最小値は 1 のままです。次に、2 を削除します。最小値は 1 のままです。次に、1 を削除します。最小値は現在 3 です。次に、3 を削除します。最小値は現在 5 です。

min(L) を実行したり、リスト全体をスキャンしたりすることなく、リストの最小値を常に追跡する良い方法があるかどうか疑問に思っています。

リストからアイテムを実際に削除するには、他のすべてを移動する必要があるため、効率が低下します。リストを毎回再ソートするのもコストがかかります。これを回避する方法はありますか？

Answer 1

最小値が削除されたときの再スキャンの現在のアプローチは、削除ごとに予想される O(1) 時間です (すべてのアイテムが削除される可能性が等しいと仮定します)。

n 個のアイテムのリストが与えられた場合、1/n の確率で再スキャンが必要になるため、各ステップで期待される作業は n * 1/n = O(1) です。