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.
