c# - 我应该在 C# 中选择哪个通用集合来维护排序的 "list"

Question

我有一个 Node 类，它有一个 float Distance 属性。

我想要一个数据结构，我可以将所有节点放入其中，并且它们将按顺序存储(例如在 AVL 树或红黑树中)。

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

我尝试使用排序字典，但事实证明它完全没用，因为他不能容纳两个距离相同的项目。

使用 list 和 Sort i 是不可能的，因为移除是 (O(n)) 并且找到 Minimum 也是 (O(n))

我所需要的只是一个简单的通用红黑树结构，它将按我将提供的某些谓词进行排序(即比较节点内的距离)

BCL中有这样的数据结构吗？

Answer 1

您想使用 c5 集合库的 TreeBag<T>类(class)。它是一棵允许重复的红黑树(因此，bag 而不是 set)。按项目值的索引访问是 O(log n)；插入和删除是 O(log n) 摊销的。

C5 Collection Library 由 Microsoft 资助；它是开源的并且免费可用。价格合适。

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