@sravan and Ashish..
In the second half of the post that starts with..
/*
@Ankur..
I will try to explain the approach with an example..
*/
i have explained how the heap-readjustment will work..
---------------
Plz go thru it and let me know if further clarification is required...
On Jan 11, 10:50 pm, Ashish Goel <ashg...@gmail.com> wrote:
> heapify/readjust (submatrix rooted at A[row+1][0] )
>
> how do we do this
>
> the element moved as part of swap may fit in anywhere in submatrixrow+1,0
> to m,n
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
>
>
>
>
>
> On Wed, Jan 11, 2012 at 11:14 PM, Lucifer <sourabhd2...@gmail.com> wrote:
> > @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 <atul.87fri...@gmail.com> 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 <sourabhd2...@gmail.com>
> > 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 <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
>
> ...
>
> 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 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.
