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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
