0

I coded the idea presented in this question: merging sorted arrays as can be seen here: Big-O complexity calculation for a merge and sort function.

As can be seen, the complexity of this approach is more than what is desirable. Is there a better approach (other than using LINQ)? What is the fundamental flaw in this approach, if any?

Community
  • 1
  • 1
Tom
  • 510
  • 1
  • 7
  • 24

1 Answers1

0

We can merge arrays in O(nk*Logk) time using Min Heap.

n= maximum size of array , k = number of arrays .

  1. Create an output array of size n*k (you can just print them also).
  2. Create a min heap of size k and insert 1st element in all the arrays into the heap
  3. Repeat following steps n*k times.
    a) Get minimum element from heap (minimum is always at root) and store it in output array (or print it).
    b) Replace heap root with next element from the array from which the element is extracted. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.

Time Complexity: The main step is 3rd step, the loop runs n*k times. In every iteration of loop, we call heapify which takes O(Logk) time.
Therefore, the time complexity is O(nk*Logk).

EDIT1 : Heapify ensures you always have min-heap , it swaps the minimum of child nodes with the parent node , if that minimum is less than parent .

This ensures that INFINITY elements will remain at bottom and the minimum element from all k arrays remain at top (root) of heap .

Aseem Goyal
  • 2,683
  • 3
  • 31
  • 48