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