次のように機能するアルゴリズムを設計しています。
最初は空の N 個のスロットがあり、各スロットには一意の番号が付けられているとします。
時間が経つと、アイテムが到着し、アイテムの番号と一致する番号のスロットに入れられます。ただし、アイテムの到着順はランダムとみなされます。
その間、マージ アルゴリズムが定期的に実行され、隣接する占有スロットをマージして、時間の経過とともにスロットがますます「接続」され、最終的に 1 つの大きな占有スロットになり、その時点でアルゴリズムが終了します。
PS私のアルゴリズムはシリアルです。一定数の新しいスロットが占有された後、マージ部分が定期的にアクティブ化されます。
おそらく、 disjoint-setに基づいたものを探しているでしょう。
n空のスロットごとにセットから始め、隣接する 2 つのスロットを埋めたら、それらを「マージ」[ユニオン] します。これは、各セットの各ルートで「最高」および「最低」フィールドを維持することによって実行できます。
要素を入力したら、そのルートを見つけて [このデータ構造で簡単に実行できます]、それをマージする必要がありますset[root.highest+1]-set[root.lowest-1]それらが両方とも既に「埋められている」場合。
マージごとに root.highest フィールドと root.lowest フィールドも変更する必要がありO(1)ますが、新しいルートが見つかったら、 で簡単に実行できます。
素集合を forests として実装する場合、アルゴリズムの初期化時間はO(n)[wherenはスロットの数] であり、各挿入 op はO(alpha(n))であり、は部分対数であるalpha(n)逆アッカーマン関数です。