How do I get the element with the smallest key in a collection, in O(1) or O(log n) time?

I know that I can use a Dictionary and retrieve an arbitrary element in O(1) time.

I know that I can get the next highest (or lowest) element in a SortedDictionary in O(1) time. But what if I wanted to remove the first value (based on TKey's ICom开发者_JS百科parable) in the SortedDictionary?

Can I use the .First() method to retrieve the smallest key? And what is its complexity? Will it run in O(1), O(log n) or O(n) time?

Is the SortedDictionary the correct data structure for this?

Note: The use case is sort of a poor man's priority queue or ordered queue. No open-source is allowed for this (must be code-from-scratch, or already in the .NET 3.5 framework).

SortedList and SortedDictionary are implemented internally as binary search trees and could ideally give you O(log n) performance for a Min (requires walking the tree, but not enumerating the whole list). However, using LINQ to perform that Min will probably enumerate the entire list.

I would consider a Skip List as a better alternative data structure.

SortedDictionary.GetEnumerator is stated as having O(log n) time - so First() should follow suit.

If you have a SortedDictionary or SortedList, you can use .First() (or dict.Keys[0] for SortedList) Otherwise, you could do:

dict[dict.Keys.Min()]

which would have overall O(N) time (as Min() must iterate the whole collection)

.First() will probably have O(1) time for a SortedList and O(log n) for SortedDictionary.

Insertion and Removal will be O(log N) time for SortedDictionary and may be up to O(N) for SortedList. Note that if you're using a dictionary to back your "priority queue" you can't have two items with the same priority.

I don't think either class has a special implementation for Last, so if you want the highest valued key, you should probably use a SortedList since you can do dict.Keys[dict.Count-1]. If you want only the highest (and not the lowest), you could use a Comparer to sort it in that order and use First.

Since you only mentioned getting values and not setting them, You could use a simple list, sort it in advance, then access any value, by order, in O(1).

Why don't you keep a separate sorted list of the keys so that you can always get the element with the smallest key just by doing dict[keyList[0]].

With an unsorted collection, getting the highest or lowest element is O(n) because any of the items could be the highest or lowest so you have to look at each. If you want to do this quickly (O(1)) you need a sorted data structure so you can infer the relative positions of values based on their location.