@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 <sourabhd2...@gmail.com> 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 <gene.ress...@gmail.com> wrote:
>
>
>
>
>
>
>
> > Think about the cost of picking the minimum. It's not O(1).
>
> > On Jan 11, 3:34 am, Sanjay Rajpal <sanjay.raj...@live.in> 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 <ankurga...@gmail.com> 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 <ankurga...@gmail.com>
> > > > wrote:
>
> > > >> @Shady Rows are already sorted ...
>
> > > >> On Wed, Jan 11, 2012 at 1:53 PM, shady <sinv...@gmail.com> wrote:
>
> > > >>> ^^ true, sort the rows and then a K-way merge.
>
> > > >>> On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal
> > > >>> <sanjay.raj...@live.in>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
> > > >>>> <yprakash....@gmail.com>wrote:
>
> > > >>>>> "sort the whole matrix in ascending array" means?
> > > >>>>> can you please explain ?
>
> > > >>>>> On Wed, Jan 11, 2012 at 12:53 PM, atul anand
> > > >>>>> <atul.87fri...@gmail.com>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 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.
>
> > > >>>> --
> > > >>>> 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.
>
> > > > --
> > > > 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.
