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