algorithm - 需要设计算法的建议

Question

我正在设计一种算法，其工作原理如下:

假设有 N 个初始为空的插槽，并且每个插槽的编号是唯一的。

随着时间的流逝，元素将到达并存放到数量匹配的插槽中项目的编号。但是，元素到达的顺序被假定为随意。

同时，会定期执行合并算法，将相邻占用的slot合并，随着时间的推移，这些slot会越来越“相连”，最终成为一个大的占用slot，此时算法终止。

附言我的算法是串行的。合并部分在一定数量后定期激活的新插槽被占用。

Answer 1

您可能正在寻找基于 disjoint-set 的内容.

从 n 集合开始，每个集合对应一个空槽，并在填满两个相邻槽后“合并”[联合] 它们。这可以通过在每个集合的每个根中维护“最高”和“最低”字段来完成。

一旦你输入一个元素，你需要找到它的根[用这个数据结构很容易做到]，并将它与 set[root.highest+1] 和 set 合并[root.lowest-1] - 如果它们都已经“填满”。

每次合并还必须修改 root.highest 和 root.lowest 字段，但是一旦找到新的根，这可以在 O(1) 中轻松完成。

如果您实现 disjoint set as forests ，算法的初始化时间为O(n) [其中n为槽数]，每次插入操作为O(alpha(n)) 其中 alpha(n) 是倒数 ackerman function , 是次对数的。