@Kumar: Form a heap with the first three elements and their sources: (1,A1), (2,A2), (12,A3). The root of the heap is (1,A1), so output the 1 and replace it with the next number from list A1: (3,A1). Reheapify, getting (2,A2), (3,A1), (12,A3). Output 2 and replace it with the next number from list A2: (4,A2). Reheapify, getting (3,A1), (4,A2), (12,A3). Output 3. etc etc etc. Eventually, the heap contains (9,A1), (10,A2), (12,A3). Output 9. Since A1 is exhausted, delete the root. This can be done by copying the last element in the heap into the root and decreasing the heap size by 1: (12,A3), (10,A2). Reheapify to (10,A2), (12,A3). Output 10 and delete (10,A2), leaving the heap (12,A3) with one node only. Output 12, replace it with 14. Output 14, replace it with 16. Output 16, replace it with 19. Output 19, replace it with 20. Output 20. The heap is empty so the process ends. Note that when only one list remains, it can be copied to the output.
Dave On Aug 2, 7:04 am, kumar raja <[email protected]> wrote: > 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.- Hide quoted text - > > - Show quoted text - -- 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.
