@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 <[email protected]> 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 <[email protected]> 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 <[email protected]>
> 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 [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.
>
> --
> 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.
>
>
--
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.
