如何在 O(1) 或 O(log n) 时间内获取集合中具有最小键的元素？
我知道我可以使用 Dictionary 并在 O(1) 时间内检索任意元素。
我知道我可以在 中获取下一个最高（或最低）元素SortedDictionary 在 O(1) 时间内。但是，如果我想删除 SortedDictionary 中的 first 值（基于 TKey 的 IComparable）怎么办？
我可以使用 .First()检索最小键的方法？它的复杂性是什么？它会在 O(1)、O(log n) 还是 O(n) 时间内运行？
SortedDictionary 是正确的数据结构吗？
注意：用例有点像穷人的优先级队列或有序队列。不允许这样做的开源（必须是从头开始的代码，或者已经在 .NET 3.5 框架中）。
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).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
SortedList 和 SortedDictionary 在内部实现为二叉搜索树，理想情况下可以为 Min 提供 O(log n) 性能（需要遍历树，但不需要枚举整个列表）。但是，使用 LINQ 执行该 Min 可能会枚举整个列表。
我认为跳过列表是更好的选择数据结构。
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 被声明为具有 O(log n) 时间 - 所以First() 应该效仿。
SortedDictionary.GetEnumerator is stated as having O(log n) time - so First() should follow suit.
如果您有
SortedDictionary或SortedList，则可以使用.First()（或dict.Keys[0] forSortedList）否则，您可以这样做：这将具有总体 O(N) 时间（因为 Min() 必须迭代整个集合）
.First()可能会有 O(1) 时间SortedList 和 SortedDictionary 的 O(log n)。对于 SortedDictionary，插入和删除的时间为 O(log N)，对于 SortedList，插入和删除的时间可能高达 O(N)。请注意，如果您使用字典来支持“优先级队列”，则不能有两个具有相同优先级的项目。
我认为这两个类都没有针对 Last 的特殊实现，因此如果您想要最高值的键，您可能应该使用 SortedList，因为您可以执行
dict.Keys[dict.Count-1]。如果您想要仅最高的（而不是最低的），您可以使用比较器按该顺序对其进行排序并使用 First。If you have a
SortedDictionaryorSortedList, you can use.First()(ordict.Keys[0]forSortedList) Otherwise, you could do: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.由于您只提到获取值而不是设置它们，
您可以使用一个简单的列表，提前对其进行排序，然后按顺序访问任何值，时间复杂度为 O(1)。
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).
为什么不保留一个单独的排序键列表，以便您始终可以通过执行
dict[keyList[0]]来获取具有最小键的元素。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]].对于未排序的集合，获取最高或最低元素的时间复杂度为 O(n)，因为任何项都可能是最高或最低，因此您必须查看每一项。如果您想快速完成此操作 (O(1))，您需要一个排序的数据结构，以便您可以根据值的位置推断值的相对位置。
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.