提案は私は次のように動作するアルゴリズムを設計してい

Question

必要とされている：

最初は空であり、各 スロットが一意に番号付けされたN個のスロットがあると仮定する。時間が経つにつれ

、アイテムが到着すると、その番号が一致し アイテムの番号のスロットに堆積します。しかし、アイテムが到着する順序は、ランダムになるべく とする。

一方、時間が経過するにつれてスロットがますます「接続」し、最終的に1つの大きな占有スロットになるように、隣接する占有スロットをマージするためのマージアルゴリズムが定期的に実行されますアルゴリズムは終了する。

P.S.私のアルゴリズムはシリアルです。合流部は、新たなスロットの が占有されている特定の番号の後に定期的に起動されます。

Answer 1

おそらくdisjoint-setに基づいて何かを探しています。

nセットでスタート、空のスロットのそれぞれ、および「マージ」[ユニオン]その次の2つの隣接するスロットを埋めたら。これは、各セットの各ルートで「最高」と「最低」フィールドを維持ことによって行うことができます。

要素を入力したら、[このデータ構造で簡単に実行できる]ルートを見つけて、set[root.highest+1]とset[root.lowest-1]とのマージを行う必要があります。

各マージではroot.highestとroot.lowestフィールドも変更する必要がありますが、新しいルートが見つかるとO(1)で簡単に行うことができます。 alpha(n)サブ対数的である逆ackerman function、ここ

もしdisjoint set as forestsを実装する場合、アルゴリズムの初期化時間がO(n)ある[nスロットの数である]、および各挿入OPはO(alpha(n))あります。スロットの容量ABT