Ok.... so here's the pseudocode...
class MyQueue
{
int? currentMinVal; //nullable
LinkedList<int> contents;
public void MyQueue()
{
contents = new LinkedList<int>();
currentMinVal = null;
}
//the regular implementations of insert and delete are below...
insert_rear, delete_front can be just as easily implemented as my
contents are in a linked list
public void Insert(int item)
{
contents.AddLast<int>(item); //add item to the linked list
//set the current min... O(1) operation
if(currentMinVal == null || currentMinVal.Value > item)
currentMinVal = item;
}
public int Delete()
{
if(!contents.IsEmpty)
{
int itemToreturn = contents.First.Value;
contents.RemoveFirst(); //some method of linked list
that removes specified element from the linked list and adjusts head
and tail pointers
if(itemToRetun == currentMinVal) // check if the
item you remove is the current minimum...
RecomputeMinValue(); //O(n) operation to
set the new minimum
return itemToReturn;
}
else
throw new InvalidOperationException();
}
public int? get_min()
{
return currentMinVal;
}
}
For this, it's not true that for all deletes, I need to do a O(n)
operation.... O(n) operation on delete is needed only if the currently
deleted item is the current min...
for Queue: 1 2 3 4 1 5 6 7 1, the linked list will have 1 ->7->6->5-
>1->4->3->2->1.... currentMinVal = 1. on first delete, since 1 is
going to be deleted, currentMin will be once again computed O(n)...
its once again 1.... on second delete, the item to be deleted is 2...
this is not the current min... so we don't do a O(n) traversal of the
list to get the new currentMin...
On Jan 11, 6:35 am, juver++ <[email protected]> wrote:
> Queue: 1 2 3 4 1 5 6 7 1. After deleting from the head, you always should
> update minimum element for O(n).
>
> However, there is another way for queue modification, so the current min is
> accessed for O(1).
> This can be done using queue and initial elements (may be in a separate
> queue).
--
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.
