Vikas, can you suggest the logic of this also? I am a bit unclear on how
the 2D arr is being used as a heap and how recursion is used to solve this
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Thu, Oct 13, 2011 at 11:37 PM, vikas <vikas.rastogi2...@gmail.com> wrote:
> @Sunny, good catch, k X k approach wont work
>
> lets try to use matrix itself as heap
>
> heapify(int cr, int cc, int Nr, int Nc){
> mr = cr; mc = cc;
> if(cr+1 < Nr)
> mr = cr+1 mc = cc;
> if(cc + 1 < Nc && min > A[cc+1][cr])
> mr = cr; mc = cc+1;
> if(A[cr][cc] > A[mr][mc]){
> swap(&A[cr][cc] ,&A[mr][mc]);
> heapify(mr, mc, Nr, Nc);
> }
>
> extract_min(){
> swap(&A[0][0], &A[hr][hc]);
> if(hc > 0) hc--;
> else if(hr > 0){
> hr --;
> hc = N;
> }
> if(hr | hc)
> heapify(0, 0, hr, hc);
> }
>
>
> }
>
>
> On Oct 13, 12:18 pm, sunny agrawal <sunny816.i...@gmail.com> wrote:
> > Nopes
> > Still it does not ensure that duplicates will not be there in the
> priority
> > queue
> >
> > what i mean is you cannot write directly
> >
> > do k times{
> > data = pop()
> > // let i,j are row and col of data
> > push(i+1,j);
> > push(i,j+1);
> >
> > }
> >
> > you need to add the following checks
> >
> > if((i+1,j) is not in the heap) push(i+1,j)
> > if((i,j+1) is not in the heap) push(i,j+1)
> > because heap does not automatically check for duplicates
> >
> > and to check for duplicates we need an extra data structure other than
> heap,
> > which stores that which (i+1,j) are already there in the heap map can
> also
> > be used so overall complexity will go O(k* lg^2K)
> >
> > On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra <
> anshumishra6...@gmail.com>wrote:
> >
> >
> >
> > > struct data
> > > {
> > > int row, col,
> > > int val;
> > > };
> >
> > > priority_queue<data> heap;
> >
> > > now fine?
> >
> > > --
> > > 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.
> >
> > --
> > Sunny Aggrawal
> > B.Tech. V year,CSI
> > Indian Institute Of Technology,Roorkee
>
> --
> 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.
