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