3
$\begingroup$

Given is an initial set of n keys. Each key k is of the form (p, q). Note that both p and q are positive.

At any given point, there are two possible actions:

1) Query-Delete: Given a value s as query, find all such keys in the set that have have the (globally) minimum p and satisfy (q >= s), and delete these keys.

2) Insert: Add a new key k' = (u, v) to the set.

I was wondering what would be the best data structure to represent the above.

My first approach is to simply sort the original set in a linked list (or array) and return the appropriate tuples when queried, and if inserted, use linear search to find the position, but the worst-case insertion then becomes O(n), while query-deletion involves checking the first element, and has the complexity O(number of distinct q values).

A second approach is to use a red-black tree with the p values as its key, storing (p, q, r) in each node, where r is the biggest q value found at that level or below in the tree.

For example, given a set (10, 4), (20, 2), (30, 2), (40, 3) the tree looks like:

        (20, 2, 4)
       /          \
 (10, 4, 4)        (30, 2, 3)
                     \
                      (40, 3, 3)

where each node is of the form (p, q, r).

This approach has the benefit of being able to early exit during the query search if (r < s) in the node. Insertion remains O(log n) like in red-black trees, but may face problems with sets of the form {(p, q1), (p, q2), ...}.

Could anyone please suggest modifications or propose a better approach? Thanks.

$\endgroup$

3 Answers 3

2
$\begingroup$

Store your data structure in a red-black tree where the first component of a key (i.e. p in (p,q)) is the key and the values are red-black trees of the second parts of keys with identical first part.

So, for the set $\{(a,b), (a,d), (d,b), (e,f), (e,g)\}$, you would store a tree with three keys (a, d, and e). The value for the key a would be a red-black tree with b and d, the for the key d would be a red-black tree with b, and the value for the key e would be a red-black tree with f and g.

A red-black tree can be split in $O(\lg n)$ time, so query-delete would take $O(\lg n) + O(\lg n) = O(\lg n)$ time - $O(\lg n)$ for the tree lookup and $O(\lg n)$ for the split of the tree. This doesn't include the cost of deleting, deconstructing, finalizing, or disposing of the deleted elements.

insert would also be $O(\lg n)$.

Query-delete can be made $O(1 + \lg k)$, where $k$ is the size of the deleted set, by keeping a pointer to the smallest key in the big tree and searching from the ends of the little tree, rather than from the root.

Amortized, query-delete is $O(1)$: using the banker's method, simply put a single on each item in the little trees. Since returning $k$ items takes $O(1 + \lg k)$ time and returns $k$ coins, its amortized cost is now $O(1)$, while insert's is $O(1 + \lg n) = O(\lg n)$.

$\endgroup$
7
  • 2
    $\begingroup$ For the hash lookup to work, we need to know what the minimum value i.e. p is, which is not provided in the query. $\endgroup$
    – forsak3n
    Mar 22, 2016 at 14:33
  • $\begingroup$ That sounds good, thank you. I cannot upvote yet, sadly. I was also wondering if it is somehow possible to make query-delete with O(1) complexity while letting insertion be O(log n) <= O(insertion) < O(n) as there will many queries. If it is not possible, could this be proved? $\endgroup$
    – forsak3n
    Mar 22, 2016 at 17:17
  • 1
    $\begingroup$ Data structure lower bounds (proving something impossible) tend to be much harder than upper bounds (proving something possible). $\endgroup$
    – jbapple
    Mar 23, 2016 at 0:29
  • 1
    $\begingroup$ @forsak3n Note that "O(log n) <= O(insertion) < O(n)" does not make much sense. You mean $T_{\mathrm{insert}} \in \Omega(\log n) \cap O(n)$. $\endgroup$
    – Raphael
    Mar 23, 2016 at 9:01
  • $\begingroup$ I've added an explanation of how query-delete is actually constant amortized time in this scheme. Operations that decrease the size of a structure can often be made constant time by simply charging the insert operation twice as much. In this case, we only need to charge it one more. $\endgroup$
    – jbapple
    Mar 23, 2016 at 12:58
1
$\begingroup$

Use treaps. They store pairs of values and are heap-ordered w.r.t. one, and BST-ordered w.r.t. the other component.

They have expected logarithmic height if the $p$'s are uniformly distributed.

Query-delete comes down to traversing the tree recursively from the root, following along all edges in "direction" of $\geq s$ as long as the priority of the current node is equal to the one you saw in the root.

$\endgroup$
4
  • $\begingroup$ What if the p's are not uniformly distributed? $\endgroup$
    – jbapple
    Mar 22, 2016 at 16:28
  • $\begingroup$ As @jbapple suggested, it is not necessary that p's be uniformly distributed. $\endgroup$
    – forsak3n
    Mar 22, 2016 at 17:21
  • $\begingroup$ @forsak3n The data structure still works, and will probably still be efficient. I don't know any analyses for non-uniform distributions, though. $\endgroup$
    – Raphael
    Mar 22, 2016 at 23:01
  • 1
    $\begingroup$ @jbapple No idea. You get some tree that may or may not have small height. My intution is that treaps are quite robust, but the OP may have to run benchmarks if they are interested in average-case performance over weird distributions. $\endgroup$
    – Raphael
    Mar 22, 2016 at 23:02
0
$\begingroup$

I would suggest C++ map with keys the first component and values map for the second component... you have logarithmic insert operation and you can erase in time linear in number of erased elements since you can access the element with the smallest first key by begin()... It's actually the interface of a red-black tree of red-black trees

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.