abt complexity. now considering worst case scenario where swapping take place every time. now assuming that we heapifying procedure , considering rows from i+1 to M as M-(i+1) 1-dimensional array . now heapify will take O(log(m*n)) time
so complexity would be M*N*log(M*N)) please correct me if i am doing wrong analysis. and about the algorithm , i have little doubt if last row after completing this procedure will remain sorted or not. On Wed, Jan 11, 2012 at 9:42 PM, atul anand <[email protected]> wrote: > @Lucifier : it seem that the sub-matrix need to be heapifyed for A[i][j] > is > > > A[i+1][j] to A[row][col] > > there is no need to include A[i][j+1] to A[i][col] for A[i][j] as you have > mentioned above. > > for eg :- > > 1 3 4 8 9 // 3 > 2 , so swap and heapify > > 2 5 18 25 50 > 6 7 22 45 55 > > we get, > > 1 2 4 8 9 > 3 5 18 25 50 > 6 7 22 45 55 > > > replace it with 4 ( 4 > 3) > we get, > > 1 2 3 8 9 > 4 5 18 25 50 > 6 7 22 45 55 > > now after heapify this highlighted array we will get 4 as a min value , > replace it with 8 ( 8 > 4) > > we get > > 1 2 3 4 9 > 8 5 18 25 50 > 6 7 22 45 55 > > after heapifying we get, > > 1 2 3 4 9 > 5 8 18 25 50 > 6 7 22 45 55 > > here 9 > 5 replace it. > > we, get > > 1 2 3 4 5 > 9 8 18 25 50 > 6 7 22 45 55 > > > after heapify we get, > > > 1 2 3 4 5 > 6 8 18 25 50 > 9 7 22 45 55 > > as we can see , 1st row is not included in the heapify procedure. > > correct me if i am wrong. > > > > On Wed, Jan 11, 2012 at 5:27 PM, Lucifer <[email protected]> wrote: > >> @Ankur.. >> >> Yes... If you follow the algo that i have presented above and use >> Atul's example you will be able to figure out.. >> >> Maybe, the confusion is regarding heapfying.. ryt?? >> I am assuming so.. >> >> Now as i said a submatrix rooted at A[i , j] is nothing but a heap >> where its subtrees share a few nodes... >> >> Now, the first thing is to visualize the heap... >> For a heap in the form of submatrix rooted at A[i][j], its children >> are subtrees in the form of submatrix rooted at A[i+][j] and A[i][j >> +1]... >> >> Now, imagine that you apply the normal heap-stabilizing approach when >> the root element of a heap is being replaced by some other value... >> Do it for an example submatrix (identified as explained above and also >> whose rows and columns are sorted) and you will see how it works... >> >> >> On Jan 11, 4:44 pm, Dipit Grover <[email protected]> wrote: >> > @Shady : you would definitely need two index variables for each array I >> > feel. >> >> -- >> 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.
