Data Structures

Question

There is a large stream of numbers coming in such as 5 6 7 2 3 1 2 3 .. What kind of data structure is suitable for this problem given the constraints that elements must be inserted in descending order and duplicates should be eliminated.

I am not looking for any code just ideas? I was thinking of a Self-Balancing BST where we could add the condition that all nodes < current node on left and all nodes > current node on right, this takes care of the duplicates .. but i don't think they are necessarily inserted in descending order. Any ideas what might be a better choice .. ofcourse it needs to be efficient time and space wise.

Answer 1

A balanced binary tree is fine. You'll locate or insert each duplicate in O(log N) time, where N is the number of elements already in the tree, so O(N log N) overall. And insertions are ordered - you can decide the order just by reversing the comparisons.

Then you just read it out once it's finished in depth first order and, voila, descending values with no duplicates.

Your stream 5 6 7 2 3 1 2 3 will result in:

    A>  5           B>  5           C>  6
                       /               / \
                      6               7   5

    D>  6           E>  6           F>  5
       / \             / \             / \
      7   5           7   3           6   2
           \             / \         /   / \
            2           5   2       7   3   1

then the final 2 and 3 are discarded since they already exist in the tree. And, when you process that tree recursively (left,current,right), you get 7, 6, 5, 3, 2, 1 as desired.

---

Another solution, if you have a limited range of numbers, is a boolean map. Let's say the input range is only the digits 0 through 9.

Set up a 10-element boolean array and set all the values to false. Them, for every number, set the corresponding value to true.

So, for your input (blank is false, t is true):

      <booleans>
      0123456789
i  5|      t
n  6|      tt
p  7|      ttt
u  2|   t  ttt
t  3|   tt ttt
|  1|  ttt ttt
|  2|  ttt ttt
V  3|  ttt ttt

the backwards-processing of the boolean map would output 7, 6, 5, 3, 2, 1.

Once all the numbers are received, go through the array in reverse order and output numbers whose values are true. This is an O(n) time operation which may take more space (it's a general rule that you can often trade off space for time when developing algorithms).

This will also work for ranges not starting at 0 - you just need to offset everything by the low end of the range. So if the range was 100 through 109, you would still have a 10-element array with the index i representing the number i + 100.

However, if the range is large and numbers sparse, I'd stick with the tree structure.

Answer 2

This depends somewhat on the ratio of duplicates to the total sample size.

High duplicate ration may just be easier to solve with either just a hash (whose keys get sorted into an ordered list once in a while), or with a combination of a hash and a blanaced tree (hash for filtering out duplicates).

Low duplicate ratio, just go with the balanced tree as you suggested.

Answer 3

Since you have got simple data that are just numbers why don't you use a binary heap stored in an array? Of course you should know an upper bound to the number of elements just to avoid reallocating it..