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 delete)...
In the amortized constant time algo, if you perform delete_rear and
delete_front in succession, it's gonna take O(n) time for each
operation... In my version, if the queue is sorted in one direction
and delete is performed on the min side, each operation will take O(n)
time...
On Jan 9, 10:49 pm, yq Zhang <zhangyunq...@gmail.com> wrote:
> 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
> > 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, 10:19 pm, SVIX <saivivekh.swaminat...@gmail.com> wrote:
> >> 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 LinkedList<int> itemsList;
>
> >> //constructor and init stuff...
>
> >> //all insert/delete methods, front, rear etc,...
> >> //one example set of insert and delete pseudocode
> >> public void Insert(int i)
> >> {
> >> if( currentMin == null || currentMin > i )
> >> currentMin = i;
>
> >> itemsList.Add(i);
> >> }
>
> >> public int Delete()
> >> {
> >> var itemToReturn = itemsList.First.Value;
> >> itemsList.RemoveFirst();
>
> >> if(itemToReturn == currentMin)
> >> RecomputeAndStoreMin(); //A private method that'll
> >> find and store min in O(n) time
>
> >> return itemToReturn;
> >> }
>
> >> public int GetMinValue()
> >> {
> >> If(currentMin == null)
> >> throw new InvalidOperationException();
> >> return currentMin;
> >> }
>
> >> }
>
> >> On Jan 9, 11:42 am, juver++ <avpostni...@gmail.com> wrote:
>
> >> > 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 unsubscribe from this group, send email to
>
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
