@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 <sourabhd2...@gmail.com> 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 <dipitgro...@gmail.com> 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 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.
