Efficient minimum discovery in lists with merge/split

Question

Suppose there are big lists (note that it is a list, not array) filled with numbers and they are unsorted.

We could merge and split these big lists. The problem is getting the minimum number in these lists with the minimum complexity.

For example, a list could have:

10 20 19 18 5 22 15 14 30 40 50 16

The minimum of this list is 5.

If we split the list at 30, we get

10 20 19 18 5 22 15 14  -> minimum is 5
30 40 50 16             -> minimum is 16

We could merge (the merge of A with B is always at the end of the A) the original list with another getting:

10 20 19 18 5 22 15 14 30 40 50 16 100 200 300 400 4 150 100 -> minimum is now 4

The minimum of the merge is trivial to obtain, but if we split the merged list again at any location then the minimum is not so trivial (at least for me). Splitting two times we would get:

10 20 19 18 5 22          -> minimum is 5
15 14 30 40 50 16 100 200 -> minimum is 14
300 400 4 150 100         -> minimum is 4

Language and memory is not an issue, we could get as much memory as needed. But if we could get an algorithm for the merge/split in O(log(N)) for all cases (best and worst case), that would be great!

Unfortunately, all my attempts to solve this are just trivial and result always in O(N). I tried to split the array in "M" and "m" sorted blocks, where "M" blocks would be blocks of numbers sorted in ascending order and "m" would be in decreasing order. But in the worst case (numbers are always going and "up" and "down") this is not efficient, at most O(N/2).

Thank you M

user_572670 · Answer

This could be done by a variation of a Skip List.

On top of your lists, you have "layers". For each two elements in layer x, you have one element in layer x+1. This element is the minimum of the elements below it. (Note that an easier implementation used non deterministic coin flip with 50% to create a layer. This makes it easier to implement, but harder to explain)

So, in your example:

5
5                      16
10          5          16
10    18    5    14    30    16
10 20 19 18 5 22 15 14 30 40 50 16

Now, both on merge and a split, you only need to modify elements from the modified element up (and not for the entire list). Since the height of the list is O(logn), you need to modify O(logn) elements.

Example, splitting at 30:

5
10          5
10    19    5    14
10 20 19 18 5 22 15 14  

16
30    16
30 40 50 16

Note that you only need to modify elements above 30 and above 10 when splitting, the rest are guaranteed to be up to date.

Note that the undeterministic property makes it handy here - you don't need to adjust the layers to much the "every 2nd element" perfectly when you use non deterministic version. This what makes it easier to implement.

Efficient minimum discovery in lists with merge/split

1 Answers