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 <[email protected]> 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" <[email protected]> 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 <[email protected]> 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++ <[email protected]> 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 > [email protected]. > > To unsubscribe from this group, send email to > > [email protected]<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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
