@atul.. Yup, its incorrect... because as i said.. for A[i][j] its children are at A[i+1][j] and A[i][j+1].. Hence, if u look at the array as a 1D array, then your LEFT and RIGHT indices would be incorrect...
Also, For any A[i][j], if it doesn't hold the correct value then the min element is always picked from A[i+1][0] and then we heapify submatrix rooted at A[i+1][0].. Nyways i think you have got this part.. but just thought of reclarifying... Let me know if u have any doubt... On Jan 11, 10:37 pm, atul anand <[email protected]> wrote: > @Lucifier : > yes i didnt hepified properly in my previous post intentionally. i only > purpose was to set min at position A[i+1][j] after heafiying.( rest i dint > care ) . > > secondly about the complexity, what i was saying > if given array is:- > > 1 3 4 8 9 > 2 5 18 25 50 > 6 7 22 45 55 > > now comparing 3 > 2 , swap we get > > 1 2 4 8 9 > 3 5 18 25 50 > 6 7 22 45 55 > now about heapifying the highlighted array , i was considering this > highlighted matrix > 3 5 18 25 50 > 6 7 22 45 55 > > as two 1-dimensional array 3 5 18 25 50 6 7 22 45 55 > > now we can apply heapify procedure to this 1-D array (bcozz in m/m this 2D > array is nothing but contiguous acquired space ) > > PARENT = floor(*i*/2) > LEFT (*i*) = 2i > RIGHT (*i*) = 2i + 1 > > is this approach is wrong ?? > > > > > > > > On Wed, Jan 11, 2012 at 10:34 PM, Lucifer <[email protected]> wrote: > > @atul.. > > > Sorry, but i don't agree with both of ur posts... > > > First of all, the complexity won't be log(m*n) for heapifying.. > > log(m*n) is valid in case of a heap represented in the form of a > > binary tree.. > > But, i have have repeatedly stressing in my previous posts that the > > submatrix heap is not a binary tree heap but rather a graph or say a > > binary tree (not really tree) where its subtrees share some nodes... > > > Disagree with the following comment.. > > /** > > 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. > > **/ > > > Also, i see that you have not properly heapified the submatrices > > correctly in the example that u have provided in the previous post.. > > > Plz go thru my last post and see if ur doubts can get clarified.. > > > --------------------------------------------- > > > Really sorry, in case previously given details by me were > > inadequate... > > Was posting in a hurry :)... > > -------------------------------------------- > > Hope, now all doubts would be cleared... > > ----------------------------------------------- > > > On Jan 11, 9:55 pm, Lucifer <[email protected]> wrote: > > > @Ankur.. > > > > I will try to explain the approach with an example.. > > > > Say the given matrix (sorted row wise and column wise) is as follows: > > > > a1 a2 a3 a4 > > > > b1 b2 b3 b4 > > > > c1 c2 c3 c4 > > > > d1 d2 d3 d4 > > > > Now, we want to sort the 2D array such that when all the rows are > > > aligned sequentially it should result in a sorted sequence.. > > > i.e. > > > > F1 F2 F3 F4 > > > ............. > > > ................ > > > F13 F14 F15 F16 > > > > such that F1 <= F2 <=....<= F16.. > > > > Now, let take each row at a time and ensure that that row contains all > > > the elements as expected in the output matrix.. > > > > Row - 1 : > > > M[0][0] = a1, which is at the correct place.. hence we won't touch > > > it.. > > > > Now our task is to pick the second smallest no. in the matrix and > > > place it at M[0][1].. > > > Currently, M[0][1] is the second smallest in Row-1, but we are not > > > sure whether its the second smallest in the entire matrix.. > > > Hence, only way we can check that is to look in the submatrix (M[1][0] > > > -- M[3][3]) > > > > Now, as we know that in the submatrix enclosed within (M[1][0] -- M[3] > > > [3]) the smallest element present in this submatrix is positioned at > > > M[1][0], therefore we will check M[0][1] against M[1][0].. > > > > If M[0][1] <= M[1][0], > > > that means M[0][1] has the second smallest element in the entire > > > matrix.. > > > else > > > M[1][0] is the second smallest element in the entire matrix and > > > we will swap M[1][0] with M[0][1].. > > > > Now, there are few things we need ensure if we end up swapping the > > > values: > > > 1) After swapping M[0][1]'s new value will be smaller than its > > > original value, therefore the following is still valid: > > > M[0][1] <= M[0][2] <=M[0][3] > > > and also as M[0][1]'s new value was previously placed below > > > M[0][0], hence it is >= M[0][0] .. > > > that means after swapping Row-1 still mains the sorted > > > order... > > > 2) Old value of M[1][0] <= M[1][1].. > > > Hence, the new value of M[0][1] is still <= M[1][1].. > > > therefore the sorted order of Column-2 is still valid... > > > 3) Now, new value of M[1][0] >= M[0][0] as an impact of old value of > > > M[0][1] >= M[0][0] > > > Also, new value of M[1][0] <= M[1][1] as an impact of > > > old value of M[0][1] <= M[1][1].. > > > [ point 3 can be proved by the using the explanation from > > > points 1 &2.. > > > 4) Now the only thing that we need to ensure is that Column - 1 is in > > > sorted order i.e M[1][0] (new) <= M[2][0] (old).. > > > If the above is true that means the submatrix enclosed within > > > (M[1][0] -- M[3][3]) is stabalized and has the row/column wise sorted > > > order property in place... > > > What if its not ?? then we need to readjust the submatrix ... > > > Once we do that we are done for the current iteration.. > > > [ we will talk abt stabalization in sometime.. lets take it for > > > granted right now..] > > > > Now, we will follow the same approach for M[0][2], so that it holds > > > the third largest element.. > > > > Once we are done with Row -1.. we have the first 4 smallest elements > > > in place and we move on to the next row and follow a same process.. > > > For ex- > > > Row -2 > > > M[1][0] is already in place and has the 5th largest element.. > > > Hence, lets look at M[1][1].. For this we will consider the submatrix > > > at (M[2][0] -- M[3][3]) and follow the same steps as > > > above.. > > > --------------------------------------------------------------------------- > > ---------------------------------------- > > > Now lets talk abt how to stabilize the submatrix when the top-left > > > corner of the submatrix is replaced with another value... > > > > Say the given matrix 'R' to be stabilized is: > > > > a b c > > > > d e f > > > > g h i > > > > Now. if 'a' replaced with 'x'... > > > > x b c > > > > d e f > > > > g h i > > > > while(1) > > > { > > > If x <= min (b,d ), // here b is nothing but the element placed next > > > to 'x' on the same row.. > > > // d is the element placed right below 'x' > > > in the same column... > > > then we are done... > > > break; > > > else > > > swap ('x', min (b,d)) > > > > } > > > > Once, we break out of the while loop, we know that the matrix has been > > > stabilized and also R[0][0] has the smallest value.. > > > > // Observe that either 'x' shifts to the right position or to the > > > position just below it.. > > > // Hence, whats the max. no. of shifts that 'x' can have.?? > > > // no. of columns + no. of rows... > > > // Hence, heapifying time is (no. of columns + no. of rows) > > > > Additional explanation: > > > Now, for matrix R[0][0], its childs when interpreted as a heap are > > > located at R[0][1] and R[1][0]... > > > > Now, we know for sure that, the submatrix (R[0][1]... R[M][N]) has the > > > smallest element at R[0][1].. > > > Similarly, submatrix (R[1][0]... R[M][N]) has the smallest element at > > > R[1][0]... > > > > If you observe closely then: > > > Elements in submatrix (R[0][0]... R[M][N]) > > > = > > > Elements in submatrix (R[0][1]... R[M][N]) > > > U > > > Elements in submatrix (R[1][0]... R[M][N]) > > > U > > > R[0][0].. > > > > Looking at the above equation we can say that, if R[0][0] has been > > > replaced and not the smallest element, then the smallest element will > > > be one of (R[1][0] or R[0][1] ).. > > > And this rule applies as we keep reducing the size of the matrix.. if > > > shifts occur as explained above.... > > > > -------------------------------------------------------- > > > > On Jan 11, 6:10 pm, Gene <[email protected]> wrote: > > > > > Think about the cost of picking the minimum. It's not O(1). > > > > > On Jan 11, 3:34 am, Sanjay Rajpal <[email protected]> wrote: > > > > > > How can it be mn log mn ? > > > > > > it will be O(mn) as we elements are sorted, we simply pick minimum > > at each > > > > > iteration of the loop. Since there are mn elements, so complexity > > will be > > > > > O(mn). > > > > > > Correct me if m wrong. > > > > > * > > > > > Sanjay Kumar > > > > > B.Tech Final Year > > > > > Department of Computer Engineering > > > > > National Institute of Technology Kurukshetra > > > > > Kurukshetra - 136119 > > > > > Haryana, India > > > > > Contact: +91-8053566286 > > > > > * > > > > > > On Wed, Jan 11, 2012 at 12:29 AM, Ankur Garg <[email protected]> > > wrote: > > > > > > If we use K merge I think the time complexity would be nm lognm > > > > > > > I think we must try doing in O(m*n) > > > > > > > On Wed, Jan 11, 2012 at 1:54 PM, Ankur Garg <[email protected]> > > wrote: > > > > > > >> @Shady Rows are already sorted ... > > > > > > >> On Wed, Jan 11, 2012 at 1:53 PM, shady <[email protected]> wrote: > > > > > > >>> ^^ true, sort the rows and then a K-way merge. > > > > > > >>> On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal < > > [email protected]>wrote: > > > > > > >>>> I guess sort the array such that elements are sorted finally in > > such a > > > > > >>>> way that if we print them row by row, the result is a sorted > > array. > > > > > > >>>> K-way merge can be useful. > > > > > >>>> * > > > > > >>>> Sanjay Kumar > > > > > >>>> B.Tech Final Year > > > > > >>>> Department of Computer Engineering > > > > > >>>> National Institute of Technology Kurukshetra > > > > > >>>> Kurukshetra - 136119 > > > > > >>>> Haryana, India > > > > > >>>> Contact: +91-8053566286 > > > > > >>>> * > > > > > > >>>> On Tue, Jan 10, 2012 at 11:28 PM, prakash y < > > [email protected]>wrote: > > > > > > >>>>> "sort the whole matrix in ascending array" means? > > > > > >>>>> can you please explain ? > > > > > > >>>>> On Wed, Jan 11, 2012 at 12:53 PM, atul anand < > > [email protected]>wrote: > > > > > > >>>>>> Given 2D array. > > ... > > read more » -- 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.
