Then it is O(n) worst case. While juver's algo is amortized constant time in
worst case.
On Jan 9, 2011 10:26 PM, "SVIX" <saivivekh.swaminat...@gmail.com> wrote:
> 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 <saivivekh.swaminat...@gmail.com> 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++ <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<algogeeks%2bunsubscr...@googlegroups.com>
.
> For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
>
--
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.
