The output is the sorted list of given lists....
On 2 August 2011 16:08, kumar raja <[email protected]> wrote:
>
> 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.
>
>
--
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.
