5

I was tutoring a student that came up with this assignment. It basically requires a data structure with the following characteristics:

  • it holds a set of integers in {1, 2, ..., n}
  • n is power of 2
  • O(log(n)) insertion, deletion and maximum
  • O(1) for determining whether an element is in the set
  • it uses only O(n) bits of storage

Does this data structure even exist?

|improve this question
  • It was recommended that this question is moved here. I didn't know about the website, and I agree. – Shoe Jan 28 '16 at 20:37
  • 2
    Wouldn't the bit vector by itself meet all these criteria, given that n is known in advance and never changes? Not to mention the storage requirement kinda rules out everything other than a bit vector all by itself (assuming the storage must be "maximum n bits", and not "O(n) bits"; gotta pick one). – Ixrec Jan 28 '16 at 20:37
  • How would you find the maximum in the bit vector in O(log(n))? – Shoe Jan 28 '16 at 20:45
  • 1
    You could use a bit vector, which exceeds all of your requirements except the maximum. (Insertion, deletion, and lookup are all O(1).) Compute the maximum lazily. You can maintain it through any sequence of insertions, but you have to invalidate it on deletion, which will force an O(n) update the next time it's queried. Depending on your access pattern, this could be quite acceptable. – Jim Mischel Jan 29 '16 at 19:51
  • 1
    @Shoe Just binary search for the last 1 – soandos Feb 1 '16 at 16:03
7

The clue to finding the right data structure here is that the requirements (other than the space requirements and direct accessibility) are those of a binary tree. This got me thinking about how you could modify a binary tree to make it meet the requirements.

What you can do is to effectively serialise into an array a pre-order breadth-first traversal of a binary tree that stores a 1 or 0 for presence of each item in the set, or for non-leaf nodes the presence of any of the child nodes. Insertion then requires O(log n) bits to be set to 1, deletion requires O(log n) bits to be copied from a could node, and maximum is a binary search. Direct access is still possible because the leaf nodes have the same format as the bit vector, ignoring the first (n-1) bits.

Example: n = 8, with items 2, 3, 4 and 6 set:

    1 11 1110 01110100
    ^ root: some values are in the set
      ^^ second level: values present in both first and second halves
         ^^^^ third level: quarters 1,2, and 3 have members, but the final quarter is empty
              ^^^^^^^^ leaves, essentially the same as the bit vector described in the question.
|improve this answer
  • Why is this needed? If it is implemented just as a bitfield where the bits represent 2^n, then 1 indicates its present, 0 absent. We can store all the numbers, insert and delete are O(1), and maximum is log(n) binary search to find the last 1 in the set) – soandos Feb 1 '16 at 16:02
  • Determining whether an element is in the set requires O(log n) effort in order to find the correct leaf; the question was for O(1). There are lessons to be learnt here from the page table structures of modern CPUs, which do indeed solve the OP's question within the parameters given. – DarthGizka Feb 1 '16 at 17:29
  • @soandas Maximum is O(n), not O(log n), because you can't determine whether there is a 1 to the right of a given point easily. That's what the additional structure gives you - the answer for each point in the array of whether you should look left or right in a binary search. – Jules Feb 1 '16 at 18:29
  • 1
    @DarthGizka testing any element is O(1) - for index i, you simply take the bit at n + i - 1. – Jules Feb 1 '16 at 18:30
  • @Jules - Sorry, I thought you meant the structure to be sparse. Mea culpa. So in effect you have two structures: a plain bit vector of size n, and a summarising index (structured like a heap) with total size n - 1 bits (i.e. n/2 + n/4 + n/8 ...) that can tell whether a given subtree is empty or not, to support the O(log n) max operation at a cost of O(log n) for updates. Exactly what the OP wanted. – DarthGizka Feb 1 '16 at 19:19

Your Answer

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

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