c# - C# 中用于查找最大值的最佳数据结构？

Question

我需要知道哪个是找到最大值的最佳数据结构，它是用 C# 实现的吗？现在我正在使用 SortedDictioniry 但它对键进行排序，基本上我不需要对键进行排序，但我需要的是一种更快的方法来找到最大值。同样在找到最大值后，我需要与该值对应的键或索引。此外，如果可以快速插入和快速删除元素，希望不超过 O(log n)。有没有这样的结构，我该如何使用它？谢谢！

Answer 1

这听起来就像一个max-heap，有很多关于如何从头开始实现的在线信息（它不是 C# 标准数据结构的一部分）。

例如，看一下这个实现，并附上详细的解释。

Answer 2

如前所述，最有效的将是最大堆。它不是 .Net 的一部分，但您可以从第三方库中进行选择，例如IntervalHeap（来自http://www.itu.dk/research/c5/）

Answer 3

您可以使用 aSortedList<TKey, TValue>或 a SortedDictionary<TKey, TValue>（就像您已经使用的那样）。另一种合适的收集类型是 Max-Heap；但是，.NET 类库不包括一个。

有关 MSDN 上的比较，另请参阅SortedList 和 SortedDictionary 集合类型。另外，如果您也想在最大值上获得快速的访问时间，那么我认为除了按键以某种方式排序之外没有其他可能性。