在c#中，我应该选择哪个泛型集合来维护排序列表

本文关键字：集合 泛型 维护 列表 排序 我应该 选择 | 更新日期: 2023-09-27 18:09:37

我有一个节点类，它有一个浮动距离属性。

我想要一个数据结构，我可以把它里面所有的节点，他们将存储排序(如在AVL树或红黑树)。

  • 我想插入O(log(n))
  • 我想检索并删除O(log(n))中的最小值

我试着使用排序字典，但它被证明是完全无用的，因为他不能容纳两个具有相同距离的项目。

使用list和Sort i排除问题，因为移除是(O(n))并且找到最小值也是(O(n))

所有我需要的是一个简单的通用红黑树结构，将排序的一些谓词我将提供(这是比较距离内节点)

BCL中有这样的数据结构吗

在c#中，我应该选择哪个泛型集合来维护排序列表

您想要使用c5 Collections Library的TreeBag<T>类。它是一个允许重复的红黑树(因此，bag而不是set)。项值的索引访问为O(log n);插入和删除是O(log n)平摊。

C5 Collection Library是由Microsoft资助的;它是开源和免费的。价格合适。

http://www.itu.dk/research/c5/

实际上，您可以使用SortedDictionary。但你需要的(假设距离是int)是SortedDictionary<int, List<Item>>。

当你想添加一个字典中没有的距离时，你插入一个新的List，包含一个单独的项目。当您想要添加字典中已经存在的距离时，请找到合适的列表并将该项目添加到其中。

要删除最小的项，找到具有最小键的List并从中删除一个项。如果List变为空，则将其从字典中删除。

由于从List的开头删除是低效的，您将需要从List的末尾删除(导致具有相同键的项的后进先出顺序)，或者使用Queue而不是List。

这可能不是最有效的解决方案，但插入，查找最小项和删除最小项都是O(log n)。

另一个选项是跳跃列表。. net框架没有，但我在c#中实现了一个。

跳跃表有O(log n)次插入、搜索和删除，其中O(1)次删除顶部项。

如果需要堆，请参见泛型二进制堆类

相关文章：