Thanks Dave ..thanks for ur elaborative explanation
On 2 August 2011 06:09, Dave <dave_and_da...@juno.com> 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 <rajkumar.cs...@gmail.com> wrote:
> > Could u please explain it with the example i have mentioned ...
> >
> > On 2 August 2011 04:42, Dave <dave_and_da...@juno.com> 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 <rajkumar.cs...@gmail.com> 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,
> > > > 10it60...@iitkgp.ac.in
> > > > 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 algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > Regards
> > Kumar Raja
> > M.Tech(SIT)
> > IIT Kharagpur,
> > 10it60...@iitkgp.ac.in
> > 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
