如何在O(1)或O(logn)时间内获得集合中键最小的元素
本文关键字：集合 元素 时间 logn | 更新日期: 2023-09-27 17:57:37
我知道我可以使用Dictionary并在O（1）时间内检索任意元素。
我知道我可以在O（1）时间内得到SortedDictionary中的下一个最高（或最低）元素。但是，如果我想删除SortedDictionary中的第一个值（基于TKey的IComparable），该怎么办？
我可以使用.First()方法来检索最小的密钥吗？它的复杂性是什么？它会在O（1）、O（log n）或O（n）时间内运行吗？
SortedDictionary是正确的数据结构吗？
注意：用例有点像穷人的优先级队列或有序队列。不允许开源（必须是从头开始的代码，或者已经在.NET3.5框架中）。
SortedList和SortedDictionary在内部实现为二进制搜索树，理想情况下可以为Min提供O（logn）性能（需要遍历树，但不枚举整个列表）。但是，使用LINQ执行该操作，Min可能会枚举整个列表。
我认为跳过列表是一种更好的替代数据结构。
SortedDictionary.GetEnumerator被声明为具有O（logn）时间，因此First（）应该紧随其后。
如果您有SortedDictionary或SortedList，您可以使用.First()（或dict.Keys[0]用于SortedList）。否则，您可以执行：
dict[dict.Keys.Min()]
它将具有总的O（N）时间（因为Min（）必须迭代整个集合）
.First()对于SortedList可能有O（1）时间，而对于SortedDictionary可能有0（logn）时间。
SortedDictionary的插入和删除时间为O（log N），SortedList的插入和移除时间可能高达O（N）。请注意，如果使用字典来支持"优先级队列"，则不能有两个具有相同优先级的项。
我不认为任何一个类都有Last的特殊实现，所以如果您想要值最高的键，您可能应该使用SortedList，因为您可以执行dict.Keys[dict.Count-1]。如果您只希望是最高的（而不是最低的），可以使用Comparer按该顺序对其进行排序，然后使用First。
由于您只提到获取值而没有设置值，您可以使用一个简单的列表，提前对其进行排序，然后按顺序访问O（1）中的任何值。
为什么不保留一个单独的键排序列表，这样只需执行dict[keyList[0]]就可以始终获得键最小的元素。
对于未排序的集合，获得最高或最低元素是O（n），因为任何项都可能是最高或最低的，所以必须查看每个项。如果你想快速做到这一点（O（1）），你需要一个排序的数据结构，这样你就可以根据值的位置推断值的相对位置。