How to get the element with the smallest key in the collection, in O (1) or O (log n)?

Question

I know that I can use Dictionary and get an arbitrary element O (1) times.

I know that I can get the next highest (or lowest) element in SortedDictionary O (1) times. But what if I wanted to remove the first value (based on TKey IComparable ) in the SortedDictionary ?

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

Is SortedDictionary correct data structure for this?

Note. A use case is a priority queue for a person or an ordered queue. Open-source is not allowed for this (it must be code-from scratch or already in the .NET 3.5 environment).

Answer 1

SortedList and SortedDictionary are implemented internally as binary search trees and ideally can give you the O (log n) performance for Min (you need to go through the tree but not list the whole list). However, using LINQ to accomplish this, Min will probably list the entire list.

I would consider the Skip List as the best alternative data structure.

Answer 2

SortedDictionary.GetEnumerator is declared as being O (log n) - so First () should follow suit.

Answer 3

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

 dict[dict.Keys.Min()] 

which would have a total time of O (N) (since Min () should iterate the whole collection)

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

Insertion and deletion will be O (log N) time for SortedDictionary and may be up to O (N) for SortedList. Please note: if you use a dictionary to support your priority queue, you cannot have two elements with the same priority.

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

Answer 4

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

Answer 5

Since you only mentioned receiving values ​​and did not set them, you can use a simple list, sort it in advance, then access any value in order in O (1).

Answer 6

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