@Jammy: No u didn't get me. Here is the explanation of what I meant: Input : two arrays a and b; and their size size_a andsize_b respectively. 1. Maxheapify both arrays 2. compare the last elements of both the arrays. If the last element of a is greater than b, swap both the elements . Then reduce the size of array b by one and again call maxhealify on this array. On the other hand if the last element of b is greater than the last element of a just decrease the size of b by one and call maxhealify on this array.Repeat this process, while taking care of the terminating condition.
I hope this helps u... If any issue notify me. thanks and regards, Ankit On Fri, Feb 25, 2011 at 8:45 AM, Jammy <xujiayiy...@gmail.com> wrote: > @ankit How do store the maximum? I know you mark the last element in > the heap invalid. But for the case above, first 80 was extracted and > then 60 should be extracted. But 60 would still lie in the first > array. > > On Feb 25, 6:10 am, ankit sambyal <ankitsamb...@gmail.com> wrote: > > Hey, it can be done in o(n*logn) time by calling maxheapify function on > the > > two arrays. Then it decreases the size of the array whose last element is > > maximum of the two arrays. I hope you are aware of heap data structure > and > > you have got the idea how to do it. If not let me know, it will explain > it. > > Though its not O(n) but still better than o(n^2). I will think of O(n) > > solution..... > > > > regards, > > Ankit > > > > > > > > > > > > > > > > On Fri, Feb 25, 2011 at 5:36 AM, bittu <shashank7andr...@gmail.com> > wrote: > > > we have two sorted array a[]={2,6,9,60}; b[]={1,3,5,34,80}; merge the > > > array in such way.. > > > a[]={1,2,3,5}; b[]={6,9,34,60,80}; ..no extra space is allowed..i.e. > > > In-Place merging > > > > > Many of you thinks its easy..but here is q. of minimum complexity i > > > have done this but min e complexity high that not seems to be gud..i > > > know it can be done O(n) I have tried in O(n^2)...so i looking for > > > some gud solution for this > > > > > here is my approach lets take two array bigger & smaller > > > > > void merge(int[] smaller, int[] bigger) > > > { > > > int ls=smaller.length; > > > int bs=bigger.length; > > > > > while(true) > > > { > > > if(smaller[ls-1]<=bigger[0]) > > > { > > > break; > > > } > > > > > //swap > > > int z=smaller[ls-1]; > > > smaller[ls-1]=bigger[0]; > > > bigger[0]=z; > > > > > //sort small > > > for(int j=ls-2; j>=0;j--) > > > { > > > if(smaller[j]<smaller[j+1]) > > > { > > > break; > > > } > > > > > int s=smaller[j+1]; > > > smaller[j+1]=smaller[j]; > > > smaller[j]=s; > > > } > > > > > //sort bigger > > > for(int j=0;j<bs-1;j++) > > > { > > > if(bigger[j]<bigger[j+1]) > > > { > > > break; > > > } > > > > > int s=bigger[j+1]; > > > bigger[j+1]=bigger[j]; > > > bigger[j]=s; > > > } > > > } > > > } > > > > > Correct me if anything missing or wrong i can improve complexity ??? > > > Hurray up!!!!!!! > > > > > Thanks & Regards > > > Shashank >>"The Best Way to Escape From The Problem is ton solve it" > > > > > -- > > > 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. > > -- > 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. > > -- 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.