What data structure should I use for these operations?

Question

I need a data structure that that stores a subset—call it S—of {1, . . . , n} (n given initially) and supports just these operations:

• Initially: n is given, S = {1, . . . , n} at the beginning.

• delete(i): Delete i from S. If i isn't in S already, no effect.

• pred(i): Return the predecessor in S of i. This means max{j ∈ S | j < i}, the greatest element in S that is strictly less than i. If there is none, return 0. The parameter i is guaranteed to be in {1, . . . , n}, but may or may not be in S.

For example, if n = 7 and S = {1, 3, 6, 7}, then pred(1) returns 0, pred(2) and pred(3) return 1.

I need to figure out:

• a data structure that represents S
• an algorithm for initialization (O(n) time)
• an algorithm for delete (O(α(n)) amortized time)
• an algorithm for pred (O(α(n)) amortized time)

Would appreciate any help (I don't need code - just the algorithms).

Answer 1

You can use Disjoint-set data structure.

Let's represent our subset as disjoint-set. Each element of the disjoint-set is an element of the subset i (including always present zero) unioned with all absent elements in the set that is greater than i and less than next set element.

Example:

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}]

Initially, we have a full set that is represented by n+1 disjoint-set elements (with zero included). Usually, every disjoint-set element is a rooted tree, and we can store the leftmost number in the element for every tree root.

Let's leftmost(i) is a leftmost value of a disjoint-set element that contains i.

leftmost(i) operation is similar to Find operation of a disjoint-set. We just go from i to the root of the element and return the leftmost number stored for the root. Complexity: O(α(n))

We can check if i is in the subset comparing i with leftmost(i). If they are equal (and i > 0) then i is in the subset.

pred(i) will be equal to leftmost(i) if i is not in the subset, and equal to leftmost(i-1) if i is in the subset. Complexity: O(α(n))

On every delete(i) operation we check if i is in the subset at first. If i is in the subset we should union an element containing i with the left neighbor element (this is the element that contains i-1). This operation is similar to Union operation of a disjoint-set. The leftmost number of resulting tree will be equal to leftmost(i-1). Complexity: O(α(n))

Edit: I've just noticed "strictly less than i" in the question, changed description a bit.