algorithm - 我应该为这些操作使用什么数据结构？

Question

我需要一个数据结构来存储 {1, . . . , n} (n 最初给出)并且只支持这些操作:

• 最初:n 是给定的，S = {1, . . . , n}开头。

• delete(i):从 S 中删除 i。如果 i 不在 S 中，则无效。

• pred(i):返回i的S中的前导。这意味着 max{j ∈ S | j < i}，S中最大的元素严格小于 i。如果没有，则返回 0。参数 i 保证在 {1, . . . , n},但可能在也可能不在 S 中。

例如，如果 n = 7 且 S = {1, 3, 6, 7}，则 pred(1) 返回 0，pred(2) 和 pred(3) 返回 1。

我需要弄清楚:

• 表示S的数据结构
• 初始化算法(O(n) 时间)
• 删除算法(O(α(n)) 摊销时间)
• pred (O(α(n)) 摊销时间) 的算法

非常感谢任何帮助(我不需要代码 - 只需要算法)。

Answer 1

您可以使用 Disjoint-set data structure .

让我们将子集表示为不相交集。不相交集的每个元素都是子集 i 的一个元素(包括始终为零)与集合中大于 i 且小于的所有缺失元素联合下一个集合元素。

例子:

n = 10
s = [1, 4, 7, 8], disjoint-set = [{0}, {1,2,3}, {4,5,6}, {7}, {8, 9, 10}]
s = [3, 5, 6, 10], disjoint-set = [{0, 1, 2}, {3, 4}, {5}, {6, 7, 8, 9}, {10}]

最初，我们有一个完整的集合，由 n+1 个不相交的集合元素(包括零)表示。通常，每个不相交集元素都是一棵有根树，我们可以在每个树根的元素中存储 leftmost 编号。

Let's leftmost(i) 是包含 i 的不相交集元素的 leftmost 值。

leftmost(i) 操作类似于Find不相交集的操作。我们只是从 i 到元素的根，并返回为根存储的 最左边 数字。 复杂度:O(α(n))

我们可以检查 i 是否在比较 i 和 leftmost(i) 的子集中。如果它们相等(并且 i > 0)，则 i 在子集中。

pred(i) 将等于 leftmost(i) 如果 i 不在子集中，则等于 leftmost(i-1) 如果 i 在子集中。 复杂度:O(α(n))

在每个delete(i) 操作中，我们首先检查i 是否在子集中。如果 i 在子集中，我们应该将包含 i 的元素与左邻元素合并(这是包含 i-1 的元素) .此操作类似于 Union不相交集的操作。 leftmost 结果树的数量将等于 leftmost(i-1)。 复杂度:O(α(n))

编辑:我刚刚注意到问题中的“严格小于我”，稍微更改了描述。