我需要一个数据结构，该数据结构存储{1，的子集(称为S)。 。 。 ，n}(最初给定的n)
并仅支持以下操作:
•最初:给出n，S = {1，。 。 。 ，n}开头。
•delete(i):从S中删除i。如果i已经不在S中，则无效。
•pred(i):返回i的S中的前任。这意味着max {j∈S | j 那绝对比我小。如果不存在，则返回0。保证参数i在{1，。中。 。 。 ，n}，
但可能在S中，也可能不在S中。
例如，如果n = 7且S = {1、3、6、7}，则pred(1)返回0，pred(2)和pred(3)返回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号存储在每个树根的元素中。让我们
leftmost(i)是包含leftmost的不交集元素的i值。leftmost(i)操作类似于不交集的Find操作。我们只是从i到元素的根，然后返回为根存储的leftmost号。 复杂度: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的元素与左邻居元素(这是包含leftmost的元素)进行合并。此操作类似于不交集的Union操作。生成的树的leftmost(i-1)编号将等于O(α(n))。 复杂度:ojit_code编辑:我刚刚注意到问题中的“严格小于i”，对描述进行了一些更改。
关于algorithm - 这些操作应使用什么数据结构？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45025165/