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++ <avpostni...@gmail.com> 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 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.