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.