<p>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:</p>

<p>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".</p>

<p>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. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-10-30T22:05:03.860Z
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?
Quanquan Liu
CC BY-SA 3.0
2014-10-30T22:11:44.270Z
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$.
daniello
CC BY-SA 3.0
2014-10-31T20:38:30.563Z
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?
Quanquan Liu
CC BY-SA 3.0
2014-10-31T21:56:48.360Z
Each merge takes $O(\log)$ time. So $t$ merges take $O(t \log n)$ time.
daniello
CC BY-SA 3.0
2014-10-30T21:22:55.633Z
2014-10-30T21:22:55.633Z
daniello
<p>I'm looking for a data structure that can do the following geometric operation:</p>

<p>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 &gt; 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?</p>

<p>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.</p>

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

CC BY-SA 3.0
2014-10-30T18:27:09.817Z
What happens to bucket b0?
Ryan Dougherty
CC BY-SA 3.0
2014-10-30T18:40:08.910Z
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$.
Quanquan Liu
<ds.algorithms><ds.data-structures>
Data structure that allows moving groups of elements into buckets
Quanquan Liu
# Data structure that allows moving groups of elements into buckets

(Asked by: username_0 on 2014-10-30)

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.

**Tags:** ds.algorithms, ds.data-structures
> **Comments:**
> **username_1**: What happens to bucket b0?  
> **username_0**: 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$.  

---

## 1 answers

### Answer by username_2 on 2014-10-30. Score: 1

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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$.  
> **username_0**: 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?  
> **username_2**: Each merge takes $O(\log)$ time. So $t$ merges take $O(t \log n)$ time.  

---

