You can do this using two stacks
---
Stack s, m;
Push(x):
s.push(x) if(x > m.top())
m.push(m.top())
else
m.push(x)
Pop():
m.pop()
return
Fine, I read it "can" be! Bone head!
Obvi can't, as some one already put it
that would mean sorting in O(n).
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email
Great!
Since we're dealing with a stack here your assertion
is that find_min doesn't change until the current
min is popped of the stack.
However,
Balaji Gopalan wrote:
>the extension of this prob asks whether one more function extract_min()
>(which returns and deletes the current minimum ) can be
"You can't sort using push-pop-findmin."
@rajivmat
push --- 4, 5, 6, 1, 3, 2 - minarray = {0,3}pop -- 4, 5, 6, 1, 3 - minarray = {0,3}pop -- 4, 5, 6, 1 - minarray = {0,3}find_min = 3rd element = 1pop -- 4, 5, 6 - minarray{0} =(Now top = mintop so minarray
I think in this way we can sort in O(n), but I cannot construct a sort
algorithm using (push-pop-findmin) so far! have you been found that?On 3/26/06, Vijay Venkat Raghavan N <[EMAIL PROTECTED]
> wrote:extract_min not possible cos that wud been a brand new sorting algorithms that runs in O(n) time.
@Prunthaban..
Could you please explain your method a little better.
Does it work for the following simulation.
push --- 4, 5, 6, 1, 3, 2
pop
pop
find_min
pop
find_min
pop
find_min
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the
extract_min not possible cos that wud been a brand new sorting algorithms that runs in O(n) time.On 3/25/06, Balaji Gopalan <
[EMAIL PROTECTED]> wrote:hithe extension of this prob asks
whether one more function extract_min() (which returns and deletes the
current minimum ) can be implemented in O(
hithe extension of this prob asks whether one more function extract_min() (which returns and deletes the current minimum ) can be implemented in O(1) time.[hint: it cant be...y?]balaji
On 3/25/06, ridvansg <[EMAIL PROTECTED]> wrote:
--~--~-~--~~~---~--~~
You recei
It seems working for me if you use arrays. It will not work if you use
LinkedList for A.
In the case of LinkedList for A the find_min will work in O(n) time.
Regards
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"
