@Kumar. Use a data structure. The comparison is only on the integer. Dave
On Aug 2, 8:20 am, kumar raja <[email protected]> wrote: > But how will u construct the heap with the pair of elements at a time like > (1,A1) .How to do that?? > > On 2 August 2011 06:18, kumar raja <[email protected]> wrote: > > > > > > > Thanks Dave ..thanks for ur elaborative explanation > > > On 2 August 2011 06:09, Dave <[email protected]> wrote: > > >> @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. > > > -- > > Regards > > Kumar Raja > > M.Tech(SIT) > > IIT Kharagpur, > > [email protected] > > 7797137043. > > 09491690115. > > -- > 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.
