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.