Let A1[ ] = {1,3,5,7,9} its size n1
Let A2 []= {2,4,6,8,10} its size n2
Let A3[]= {12,14,16,19,20} its size n3
k=3 sorted lists are given to us.
n= n1+n2+n3
If i want to merge them using Heap how to do that ??
I have an idea ,but i am could not able to understand whether it is
right/wrong and what is its time complexity??
solution :
I will take the first element in each list and create a heap and sort it
out.
It has complexity of O(k logk) . the remaining elements are inserted into
Heap one by one and it will take O(log h) (h is the height of heap) to
insert the new element.
But the height of the heap is keep on increasing as we insert more and more
elements into it. So i think 'h' cant be a constant ,what should be the
value of h???
So the complexity comes down to O( (n-k) log h) .because n-k elements are
left to be inserted and each insertion takes O(log h) time.
I want the correct analysis for this problem .
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
[email protected]
7797137043.
09491690115.
--
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.
