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

Question

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 IComparable) 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).

Answer 1

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.

Answer 2

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

Answer 3

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.