@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. > > > > > > >>>>>> The rows are sorted in ascending order and the colums are > sorted in > > > > >>>>>> ascending order. > > > > > > >>>>>> We have to sort the whole matrix in ascending array. > > > > > > >>>>>> We cannot use extra space. > > > > > > >>>>>> -- > > > > >>>>>> 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. > > > > > > >>>> -- > > > > >>>> 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. > > > > > > > -- > > > > > 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. > > -- 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.
