Could u please explain it with the example i have mentioned ... On 2 August 2011 04:42, Dave <[email protected]> wrote:
> @Kumar: As you said, insert one number from each list into the heap. > Accompany the number with an indication of which list it came from. > The minimum number is now at the root of the heap. Output it, replace > it with the next number in the same list, and restore the heap > condition. When a list is exhausted, delete its entry from the heap > and restore the heap condition with the smaller heap. When the entire > heap is exhausted, the sorted data is output. Complexity is k log k + > (n-k) log k = n log k. > > Dave > > On Aug 2, 5:38 am, 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. > > -- > 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. > > -- 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.
