Data Structure - Array of Array

Question

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.

However, I think it is asking about Abstract Data Structures that were taught at a class. We are taught about Priority Queue ADT, Stack ADT, Queue ADT, and heap so far.

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

Thank you,

Answer 1

You would like to have the ability to extract the minimal array (in terms of length), then extract the next minimal, merge them, and insert them back to the data structure.

Since you want the best performance possible, you now would like to ask yourself how much each operation would cost?

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.

*Note that the complexity times I wrote here are disregarding the length of the arrays themselves. I treated them as simple elements for simplicity, since the question focuses on the use of the data structure.