Algorithm for splitting an array into k sub-arrays

Question

We want implement a data structure that have the following methods: Init(A,k)- Gets an array A with n different values and initialize our data structure that so it will divide A into k equally sized sub-arrays (+-1), that each value in the i'th sub-array will be larger than any value in the (i-1)'th sub-array, and smaller than any value in the (i+1)'th sub-array. This method need to be applied in complexity of O(n log k).

Insert(x)- Gets a value x which isn't in our data structure, and adds it. This method need to be applied in complexity of O(k logn).

I did the init method using Medians- ofMedians QuickSelect, by dividing the array into k' sub arrays when k' equals to the closest power of 2 for k, and then I adjusted my pointers to the dividers by using Select on the smaller arrays which added me only O(n).

With the Insert part I'm having some trouble and would appreciate any help, Thanks:)

Answer 1

Insert$(x)$ can be implemented in $O(k \log(n/k))$ time. I will use the terms subarray and group interchangeably.

Let $n$ be the number of elements in the data structure before the insert operation. We will maintain this invariant: each subarray contains either $\lfloor n/k \rfloor$ or $\lceil n/k \rceil$ elements. The elements of each subarray are stored in a min-heap and in a max-heap that support element deletion.

Insert $x$ into the unique group $i$ whose minimum element is smaller than $x$ and such that the minimum element of the next group (if any) is larger than $x$.

Notice that if, before the insert operation, $i$ contained $\lfloor n/k \rfloor$ elements then the operation cannot possibly violate the invariant. This means that if the invariant is violated then $\lfloor n/k \rfloor < \lceil n/k \rceil$, $i$ contained $\lceil n/k \rceil$ elements, and there is a group $j \neq i$ that contained $\lfloor n/k \rfloor$ elements. Let $j^*$ be the value of $j$ that satisfies the above conditions and minimizes $|j^*-i|$.

We can restore the invariant as follows:

• If $j^* < i$ then all groups $h \in \{j^*+1, \dots, i-1\}$ have $\lceil n/k \rceil$ elements. For each $h= j^*+1, \dots, i$ do the following: pick the minimum element $m$ from group $h$ (this can be done in $O(\log n/k)$ time by a pop() operation on the min-heap of $h$ and a delete($m$) operation on the max-heap of $h$) and add $m$ to group $h-1$ (this amounts to adding $m$ to both the min-heap and the max-heap of group $h-1$).

• If $j^* > i$ then all groups $h \in \{i+1, \dots, j^*-1\}$ have $\lceil n/k \rceil$ elements. For each $h= i, \dots, j^*-1$ do the following: pick the maximum element $M$ from group $h$ and add it to group $h+1$.