1. First take two lists at a time and merge them so total elements parsed
for all lists =O(n)
This operation results in k/2 lists
2. Repeat steps till k/2 == 1.
*Time complexity of above solution = O(n logk)*
Step1 would loop through *logk *times and each operation would require
parsing all n elements in all the lists for making k/2 lists
eg:: if i had 8 lists then first pass would make 4 lists by parsing all n
elements; second pass would make 2 lists by parsing again n elements and
third pass would give 1 list again by parsing n elements.
*Constraint of the above Solution*
For merging we would require *O(n) *extra space.
*Solution2: Without Using O(n) extra space; uses O(k) extra space*
**j = 1;
1. (For all lists L[i])
{
Take the jth element from each list and create a min heap in O(k) with the
node data and
index information. Take the minimum element from the heap in O(1) i.e. root
node and put
it in *List1 indexj.*
**if the element didn't belong to list1[j] then swap it with list1[j] with
list to which the min
element belonged.
Now increment the pointer j for the list l1(or to the list where in the min
nodes are getting added) and add the new node to min heap
}
2. Keep repeating steps 1 till all n elements are being looked up
*Time Complexity = O(n logk ) SPACE = O(k)*
At a time we have k elements min heap and for all n elements we have to
readjust the heap in log(k) time so total time = *O(n logk )* and space used
= *O(k)*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
