I have a set S of (key, value) pairs and a large number of subsets of S. I'm looking for a data structure that would efficiently execute the following operations :

  • Add a (key, value) pair to S and to a collection of subsets.

  • Delete a (key, value) pair from a collection of subsets containing this pair (not all of them).

  • Return the max value of a subset.

Right now my solution is to have, for every subset, a binary heap coupled with a hash table (so I can access the element I want to delete in constant time).

I wonder if there's a more efficient way to do this that would capitalize on the fact that these subsets have elements in common (so sorting them for every subset sounds like a bit of a waste).

  • $\begingroup$ Please add a reference to the original problem(s). Why is this important? 1) Credit could be attributed. 2) The original problem statement is probably more detailed and more specific. 3) A reference is apt to motivate people. 4) A reference may save readers who look for related materials lots of time. $\endgroup$ – Apass.Jack Jan 22 at 13:01
  • $\begingroup$ This is a generalized version of a problem I'm not allowed to disclose the source of. $\endgroup$ – RcnSc Jan 22 at 14:23
  • 1
    $\begingroup$ Can you describe any structure of that "large number of subsets of S"? $\endgroup$ – Apass.Jack Jan 22 at 14:36
  • $\begingroup$ @Apass.Jack I realize that my question might be too broad. I'll write a more specific version of this problem in about a week. $\endgroup$ – RcnSc Jan 22 at 14:57
  • $\begingroup$ Try looking up Segment Trees and Fenwick Trees. These definitely have to be altered to fit your particular model. Range Minimum Query Data Structures were exclusively developed to help model such questions. $\endgroup$ – Sagnik Jan 22 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.