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,

  • $\begingroup$ 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. $\endgroup$ – D.W. May 14 '18 at 20:37
  • $\begingroup$ @D.W. This is the question asked unfortunately . $\endgroup$ – user87320 May 14 '18 at 20:45
  • $\begingroup$ OK. Where did you see this question? Please edit the question to credit the source of this question. $\endgroup$ – D.W. May 14 '18 at 20:47
  • $\begingroup$ @D.W. I think this is from old lecture note from my friend. $\endgroup$ – user87320 May 14 '18 at 21:56

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy