Given k sorted arrays of size n each, merge them and print the sorted output.
Example:
Method 1 - Merging from 1 array to other
It does so by using the "merge" routine central to the merge sort algorithm to merge array 1 to array 2, and then array 3 to this merged array, and so on until all k arrays have merged.
Time complexity - O(n . k^2)
Method 2 - Merge 2 at a time, again and again.
Step 1: Merge arrays (1 and 2), arrays (3 and 4), and so on. (k/2 array merges of 2n, total work kn).
Step 2: Merge array (1,2 and 3,4), arrays (5,6 and 7,8), and so on (k/4 merges of 4n, total work kn).
Step 3: Repeat...
There will be log(k) such "Steps", each with kn work. Hence total work done = O(k.n.log(k)).
Even otherwise, if we were to just sort all the elements of the array we could still merge everything in O(k.n.log(k.n)) time.
Method 3 - Maintain k min heaps, and get the min element from all the arrays and saving into one
A simple solution is to create an output array of size n*k and one by one copy all arrays to it. Finally, sort the output array using any O(nLogn) sorting algorithm. This approach takes O(nkLognk) time.
We can merge arrays in O(nk*Logk) time using Mean Heap. Following is detailed algorithm.
1. Create an output array of size n*k.
2. Create a min heap of size k and insert 1st element in all the arrays into a 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.
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.
Source
http://stackoverflow.com/questions/11026219/why-is-k-way-merge-onk2
http://www.geeksforgeeks.org/merge-k-sorted-arrays/
Example:
Input:
k = 3, n = 4
arr[][] = { {1, 3, 5, 7},
{2, 4, 6, 8},
{0, 9, 10, 11}} ;
Output: 0 1 2 3 4 5 6 7 8 9 10 11
Method 1 - Merging from 1 array to other
It does so by using the "merge" routine central to the merge sort algorithm to merge array 1 to array 2, and then array 3 to this merged array, and so on until all k arrays have merged.
Time complexity - O(n . k^2)
It doesn't traverse each of the k arrays once.
The first array is traversed k-1 times, the first as
merge(array-1,array-2), the second as merge(merge(array-1, array-2),
array-3) ... and so on.
The result is k-1 merges with an average size of n*(k+1)/2 giving a complexity of O(n*(k^2-1)/2) which is O(nk^2).
The mistake you made was forgetting that the merges are done serially rather than in parallel, so the arrays are not all size n.
The result is k-1 merges with an average size of n*(k+1)/2 giving a complexity of O(n*(k^2-1)/2) which is O(nk^2).
The mistake you made was forgetting that the merges are done serially rather than in parallel, so the arrays are not all size n.
Method 2 - Merge 2 at a time, again and again.
Step 1: Merge arrays (1 and 2), arrays (3 and 4), and so on. (k/2 array merges of 2n, total work kn).
Step 2: Merge array (1,2 and 3,4), arrays (5,6 and 7,8), and so on (k/4 merges of 4n, total work kn).
Step 3: Repeat...
There will be log(k) such "Steps", each with kn work. Hence total work done = O(k.n.log(k)).
Even otherwise, if we were to just sort all the elements of the array we could still merge everything in O(k.n.log(k.n)) time.
Method 3 - Maintain k min heaps, and get the min element from all the arrays and saving into one
A simple solution is to create an output array of size n*k and one by one copy all arrays to it. Finally, sort the output array using any O(nLogn) sorting algorithm. This approach takes O(nkLognk) time.
We can merge arrays in O(nk*Logk) time using Mean Heap. Following is detailed algorithm.
1. Create an output array of size n*k.
2. Create a min heap of size k and insert 1st element in all the arrays into a 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.
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.
Source
http://stackoverflow.com/questions/11026219/why-is-k-way-merge-onk2
http://www.geeksforgeeks.org/merge-k-sorted-arrays/
0 comments:
Post a Comment