algorithm - 要素が [a,b] で重み付けされているランダムな削除と挿入を実現するデータ構造

Question

各要素が[a、b]に従って重みを持つ要素の配列が与えられた場合、一定時間の挿入と削除を実現できるように、データ構造とアルゴリズムを設計したいと思います。削除はランダムに実行され、要素が削除される確率はその重みに比例します。

両方の操作を一定時間で達成できる決定論的アルゴリズムがあるとは思いませんが、これを達成できるランダム化されたアルゴリズムがあると思いますか?

Answer 1

これは答えのスケッチです。

重みが 1 のみの場合、入力のランダム順列を維持できます。要素が挿入されるたびに、それを配列の最後に置き、配列i内のランダムな位置を選択し、最後の要素を位置の要素と交換しiます。（ランダムな位置が最後のものであることが判明した場合、何もしない可能性があります。）削除する場合は、最後の要素を削除するだけです。

O(1) (最悪の場合または償却) の挿入と削除で動的配列を使用できると仮定すると、これは O(1) で挿入と削除の両方を行います。

---

重み 1 と 2 では、同様の構造を使用できます。おそらく、重み 2 の各要素は、1 回ではなく 2 回配置する必要があります。おそらく、重み 2 の要素が削除されると、その他のコピーも削除されるべきです。したがって、実際には、要素の代わりにインデックスを格納する必要があり、locations各要素の 2 つのインデックスを格納して追跡する別の配列 を格納する必要があります。スワップにより、このlocationsアレイが最新の状態に保たれます。

任意の要素の削除は、挿入と同様に O(1) で実行できます。最後の要素と交換し、最後の要素を削除します。