@all
I have come across this question earlier. it's a young's tableaus (
cormen pg. 167 ) can be treated as min heap. solution can be found in
mit online study material.
i'll post the link here as soon as i remember it.
On 1/24/12, atul anand atul.87fri...@gmail.com wrote:
@praveen : k way
This can be done... k way merge...
c- number of columns
r- number of rows
In O(c*r*log(r))
PRAVEEN RAJ
DELHI COLLEGE OF ENGINEERING
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
@praveen : k way merge would require extra space right??question is to
do it in place.
On Tue, Jan 24, 2012 at 5:47 PM, praveen raj praveen0...@gmail.com wrote:
This can be done... k way merge...
c- number of columns
r- number of rows
In O(c*r*log(r))
PRAVEEN RAJ
DELHI COLLEGE OF
@lucifer:nice explanation !... just to make a small clarification, in your
stabilisation part u jus compare x with min (b,d) , make a swap if
necessary and then next time u compare it shud be =min(b,d) and so u
break.
x b c
d e f
g h i
so now after breaking x is less than both b
@lucifer: yes I get that...I was just saying that after a swap has happened
within the while loop ( since x min(b,d) might have been the case ) ,
then in the next looping within while, break wud happen right? meaning it
doesnt stay in the while after a swap happens...
On Sun, Jan 22, 2012 at
@ lucifer: thank you !
On Sun, Jan 22, 2012 at 4:12 PM, Lucifer sourabhd2...@gmail.com wrote:
@Arun,
Nope.. the loop exits only when there are no more swaps possible...
Let me explain with an example..
x b c
d e f
g h i
say x min(b,d) , where min(b,d) = b,
Hence, swap
@prakash...ya i realized that and it will be sorted row and column
wise.which will become same as forming min-heapand my algo will
become same what lucifer had already specified...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
@ all k-way people : I dont get it how the complexity would be O(m*n) . I
just went through the algo and I feel that one would need to find the
minimum element among the head-elements of all individual row-arrays, for
all the resulting m*n elements. I say so since we may not necessarily have
a
any idea on how to merge two sorted arrays of size m and size n in O(m+n)
time and without extra space ?
On Wed, Jan 11, 2012 at 3:22 PM, Dipit Grover dipitgro...@gmail.com wrote:
@ all k-way people : I dont get it how the complexity would be O(m*n) . I
just went through the algo and I feel
@shady :
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514rep=rep1type=pdf
it is not easy to merge sorted array inplace.
check this link..hope this help.
On Wed, Jan 11, 2012 at 4:53 PM, shady sinv...@gmail.com wrote:
any idea on how to merge two sorted arrays of size m and size
i have little doubt in complexity of proposed algo..
aren't we including complexity of heapifying each time. ??
On Wed, Jan 11, 2012 at 2:57 PM, Lucifer sourabhd2...@gmail.com wrote:
@dipit ..
Yup you are correct..
Say, no of rows = M and no. of cols = N,
Time complexity = sum over all i
@Lucifer
I am not getting how u r working with heapifying each time ..
Initially the array is such that minimum value is ay (0,0) and and max at
index (m-1,n-1)
Now when u swap a value
Then u heapify i.e. make the prior arrangement again but that in turn will
lead to few swaps and so
@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
sorry I mean 1 variable per each array
--
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
@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
abt complexity.
now considering worst case scenario where swapping take place every time.
now assuming that we heapifying procedure , considering rows from i+1 to M
as M-(i+1) 1-dimensional array .
now heapify will take O(log(m*n)) time
so complexity would be M*N*log(M*N))
please correct me if i
@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 ,
correction : /*set min at position A[i+1][0] after heafiying */
On Wed, Jan 11, 2012 at 11:07 PM, atul anand atul.87fri...@gmail.comwrote:
@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
I thought of a simpler algo, i m using the property of this matrix
That is. a[i][0] is smallest of a[i][] and a[i+1][]so on,so to
decide next smallest element i will only consider
a[i][0]...
i will swap element if required and sort the row(too by swapping) if
element are changed.
on the
I thought of a simpler algo, i m using the property of this matrix
That is. a[i][0] is smallest of a[i][] and a[i+1][]so on,so to
decide next smallest element i will only consider
a[i][0]...
i will swap element if required and sort the row(too by swapping) if
element are changed.
on the
20 matches
Mail list logo
