# Data Structure - Array of Array

Suppose that we have a family $F=\{a_1,\dots,a_s\}$ of sorted arrays to merge. Our strategy is to choose two of them, say $a_i$ and $a_j$, remove them from $F$, merge them and put the resulting array back into $F$; we keep doing that until there is only one array in $F$. We will use a greedy strategy: at each step, we choose $a_i$ of minimal length in $F$, and $a_j$ of minimal length in $F-\{a_i\}$.

What data structure would you use to store $F$?

Obviously, I assumed F $F$ be an array of array as each element of F is an array of integers.

Can F be one of them? If so, please explain why F can be such structure.

Thank you,

• Why do you think that the best strategy is to pull out two arrays from $F$, merge them, put the result back in, and repeat? I doubt that is optimal. Are you sure that's the question you want to ask? Or are you open to different solutions? If so, you might want to edit the question to reflect the problem you really want to solve, without assuming what shape the best solution will take.
– D.W.
May 14, 2018 at 20:37
• @D.W. This is the question asked unfortunately .
– user87320
May 14, 2018 at 20:45
• OK. Where did you see this question? Please edit the question to credit the source of this question.
– D.W.
May 14, 2018 at 20:47
• @D.W. I think this is from old lecture note from my friend.
– user87320
May 14, 2018 at 21:56

If you use a stack you would have the option to $pop$, which is good if you assume your stack is given you with the arrays already sorted by length (will be $O(1)$). So, you will be able to $pop$ the first two arrays and then merge them. But now, what will you do with the merged array? You have no guarantee that the new array is indeed the shortest one. A simple queue won't do as well.
So, a better option would be to use a priority queue, implemented as a heap. You will have a heap where the values are the length of the arrays. To get the two shortest array you will use $extract-min$. You can use Fibonacci heaps which will give you $O(\log n)$ amortized for extraction. Next, after merging the arrays you can insert it back with $O(1)$ amortized time complexity.