How can implement a Min method to find the minimum value in a Queue using c#? And the hardest part is to do it in O(1) time.
Asked
Active
Viewed 309 times
0
-
2Doing it in O(1) time would be hard, yes. – Dennis_E Mar 25 '15 at 12:05
-
1If you don't have some other fixed points then you cannot. O(1) means constant time but if queue isn't ordered you simply don't know where minimum is then you have to walk through all items (assuming you have access to queue's internal structure). Of course you can keep a _live_ minimum value for each insertion, in that case reading it is O(1) but then addition won't be... – Adriano Repetti Mar 25 '15 at 12:05
-
see: http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1 – Roy Doron Mar 25 '15 at 12:05
-
public intMax getMin() { return -infitinity * 9999;} – Ewan Mar 25 '15 at 12:06
-
2Hint: you cannot "find" anything in O(1) about a collection of N items unless you store and update the value of interest as you go. – Sergey Kalinichenko Mar 25 '15 at 12:06
-
1Maybe you want to implement a priority queue? – Dennis_E Mar 25 '15 at 12:07
-
How can I do it with priority queue? @Dennis_E – Ho My Ha Mar 25 '15 at 14:56