Implement a queue in which push_rear(), pop_front() and get_min() are
all constant time operations.
How about a circular doubly linked list for the push and pop, and then
a priority queue for the min?
--
You received this message because you are subscribed to the Google Groups
Algorithm
@above
What is the complexity of the pop_front() operation?
--
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
@above
What is the complexity of the pop_front() operation?
O(1)
--
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
@above
Really? When one removes head then, min element should be updated.
--
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
@juver, thanks for the explanation... but a few more queries...
In my implementation, when I delete first element, why should we
access all other elements? I should do that if the element i'm
deleting is the current minimum...
or is my understanding of get_min() totally wrong? I assumed
You are right about purpose of get_min().
Please post detailed pseudocode for each operation.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send
Queue: 1 2 3 4 1 5 6 7 1. After deleting from the head, you always should
update minimum element for O(n).
However, there is another way for queue modification, so the current min is
accessed for O(1).
This can be done using queue and initial elements (may be in a separate
queue).
--
You
Ok so here's the pseudocode...
class MyQueue
{
int? currentMinVal; //nullable
LinkedListint contents;
public void MyQueue()
{
contents = new LinkedListint();
currentMinVal = null;
}
//the regular implementations of insert and delete are
And what about the 1 2 3 1 1 1 1 1 1 1 3 5 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1.
Your algo is inefficient in all cases.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To
The best way to check your algo on practice, generate a very big test case
with many operations.
Check the time and amount of accesses for each element.
In your case you have O(n) for the operation on average.
--
You received this message because you are subscribed to the Google Groups
yes... thats true... for the amortized constant time algo, u do a O(n)
operation for one of the delete operations... my version does a O(n)
operation for deletes of the min element... Min element can be deleted
only when it's either in the front or at the back (using delete_front
or the regular
You should analyze your algo more precisely and study something about
amortized time complexity.
Your delete operation takes O(n) time for EVERY query.
So for the sequence of M deletetions there is an average time O(N) which is
NOT constant on the worst case.
--
You received this message
@ Juver,
I got the following response in the group digest mail. It'll be great
if you can provide some inputs so I can refine my understanding...
Could you please help me understand how my delete operation takes O(n)
time for every delete? I propose to maintain the minimum at the queue
level
About 2 stack implementation.
Yes some operations can be O(n) as a separate estimation. But all other will
be constant, cause we access elements at most twice.
So for the sequence of M operations (pop,push,min) total complexity will be
O(M), so the average cost of each operations is O(1).
There
Use a linked list (maintain both head and tail positions) and treat it
as a queue insert/delete front or back... whatever...
For each insert, see if it's less than the current min and maintain
min... If you're deleting the current min, you may traverse from head
to tail and recompute the
All operations should constant at least on average.
So your idea is not suitable.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
why's the linked list option not constant (at least for most cases)?
the time's not constant only for delete operation (that too only if
you delete the current min)... otherwise, everything is a O(1)
operation...
get_min() already has the min...
push_rear(), pop_front() - you're maintaining the
When you remove element from the front of queue, you should update min value
for all remaining nodes.
So it's linear.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To
I think you misunderstood my solution...
There's no min value for each node here... The queue class i propose
will look like this...
public class MyQ
{
private int? currentMin; //nullable current minimum val in the
queue
private LinkedListint itemsList;
//constructor and init
The only operation for which this solution doesn't have constant time
(variable based on number of items in the list) is for 'delete' and
that too when the minimum item is deleted. For all other cases, delete
is constant as well... For delete in those special cases, time is
O(n)...
On Jan 9,
Then it is O(n) worst case. While juver's algo is amortized constant time in
worst case.
On Jan 9, 2011 10:26 PM, SVIX saivivekh.swaminat...@gmail.com wrote:
The only operation for which this solution doesn't have constant time
(variable based on number of items in the list) is for 'delete' and
@Juvier, @yq Zhang
In your approach, when you are asked pop_front() you keep popping from
one stack and pushing them to another and then from the other pop the
top element. What happens is this top element happens to have been the
Min element?Example
stack1 {(2,2),(4,2),(3,2),(6,2)} (a,b) = (
When you push into stack2, you have to recompute the min value. So after you
push into stack2, it will be:
(6,6),(3,3),(4,3),(2,2)
On Thu, Jan 6, 2011 at 6:34 PM, sourav souravs...@gmail.com wrote:
@Juvier, @yq Zhang
In your approach, when you are asked pop_front() you keep popping from
one
only 2 stacks, one of them (or both...) should provide functionality for
retrieving minimum.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send
Good point. Right.
But we can avoid first stack of such structure, having separate variable
(Minimum) for this.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe
That's a big save of space!
On Jan 5, 2011 9:03 AM, juver++ avpostni...@gmail.com wrote:
Good point. Right.
But we can avoid first stack of such structure, having separate variable
(Minimum) for this.
--
You received this message because you are subscribed to the Google Groups
Algorithm
Yes, you are right. Stack contains the following pair of elements - (Min,
Element),
where Min - minimum element among all elements in the stack below the
current,
Element - current element. When you add new element onto the stack, then you
should
push pair(min(stack.top().Min, Element),
@yq Zhang,
To pop if you are going to pop all from first stack and push into the
second stack, then does your operation remain constant time? Please
note that we need constant time implementation for the 3 functions
pop_front, push_rear and get_min(). Goint by your approach, not all of
them are
Simulate queue using two stacks.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more
@juver++ how will implwment find_min() function?
On Sun, Jan 2, 2011 at 2:33 PM, juver++ avpostni...@gmail.com wrote:
Simulate queue using two stacks.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
keep min for stack is easy. just use another stack to keep the min for each
top.
Sent from Nexus one
On Jan 2, 2011 11:43 AM, Anuj Kumar anuj.bhambh...@gmail.com wrote:
@juver++ how will implwment find_min() function?
On Sun, Jan 2, 2011 at 2:33 PM, juver++ avpostni...@gmail.com wrote:
31 matches
Mail list logo
