@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.
