0
$\begingroup$

I'm looking for a data structure that can do the following geometric operation:

Suppose there are a set of buckets $b_0, b_1..., b_n$ each of which contains some elements. Suppose I want to move all the elements in buckets $b_i$ where $i > k$ one bucket forward. So the elements in bucket $b_{k+1}$ would be moved to bucket $b_k$ and the elements in bucket $b_{k+2}$ would be moved to bucket $b_{k+1}$ and so on. The obvious way to move these elements is to go to each bucket and shift all the elements into the previous bucket. But is there a data structure that will allow me to move the buckets all at once?

I used buckets in the description because it's easier to formulate the question in terms of buckets. But the data structure doesn't necessarily have to be buckets. All I need is a data structure that can allow me to move "chunks" of elements in one go (for example shifting consecutive the buckets $x$ number of buckets forward all at once) and then allow me to query the structure as normal (for example, allow me to query $b_{k}$ now with all the elements shifted.

EDIT: I'm mainly interested in whether an already existing data structure that I'm not aware of does this.

$\endgroup$
  • 1
    $\begingroup$ What happens to bucket b0? $\endgroup$ – Ryan Oct 30 '14 at 18:27
  • $\begingroup$ if there are no buckets less than bucket $b_k$, then all the elements stay in the current bucket $b_k$. So all elements in bucket $b_0$ if it's moved down would stay in bucket $b_0$. $\endgroup$ – Quanquan Liu Oct 30 '14 at 18:40
1
$\begingroup$

I don't quite know if this is what you were looking for since it is not a single data structure that has a name - but what you are asking for is easily implementable using just a linked list and a binary search tree:

Keep a single linked list where all the elements of bucket $i$ come before the elements of bucket $i+1$. On every link you can have a boolean flag - is this the same bucket or next bucket. Now doing the shift corresponds to setting the flag to "same bucket" from "next bucket".

Of course you probably also want to maintain some way to see the first element of each bucket. A way to do this is to store the pointers to the first element of each bucket in a balanced binary search tree, such that the key of the pointer to bucket $i$ is $i$. The search tree should be able to: (a) given $i$, output the entry with the $i$'th lowest key and (b) delete entries from the search tree.

Merging bucket $i$ and $i+1$ now reduces to finding the entry in the search tree with the $i+1$'st lowest key, deleting this entry from the search tree, going to where it points in the list, and setting the flag of the arc pointing into this node in the list to "same bucket". Thus all operations take $O(\log n)$ time.

Note that after some "shift" operations are performed the key of the $i$'th bucket is no longer $i$, but it is the $i$'th lowest key stored in the search tree.

$\endgroup$
  • $\begingroup$ Not totally sure because I just skimmed this answer. But it doesn't allow moving a bucket more than once? Ie. if I wanted to move a set of buckets one down. Then I want to move another set of buckets one down but the sets of buckets have intersections so a subset of both sets could move more than once down. I'm not sure if this solution solves this problem? $\endgroup$ – Quanquan Liu Oct 30 '14 at 22:05
  • $\begingroup$ The solution handles this: suppose we start with 6 buckets and 15 elements: $1,2,3|4,5|6,7|8,9,10|11,12|13,14,15$. The binary search tree stores: $1,4,6,8,11,13$ (and pointers to them in the list). Then you merge bucket 3 and 4 - then you get: $1,2,3|4,5|6,7,8,9,10|11,12|13,14,15$ with $1,4,6,11,13$. Merge $3$ and $4$ again to get $1,2,3|4,5|6,7,8,9,10,11,12|13,14,15$ with $1,4,6,13$. $\endgroup$ – daniello Oct 30 '14 at 22:11
  • $\begingroup$ Ah thanks for the explanation. Looked at it more closely now, and I think it can handle up to one merge in $O(log n)$ time. If you have multiple merges, you potentially do $O(n \log n)$ work right? $\endgroup$ – Quanquan Liu Oct 31 '14 at 20:38
  • $\begingroup$ Each merge takes $O(\log)$ time. So $t$ merges take $O(t \log n)$ time. $\endgroup$ – daniello Oct 31 '14 at 21:56

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.