维护排序列表

Question

我需要存储节点的集合：

class Node
{
   int Value;
   //other info
}

我有三个要求：

1. 需要能够有效地检索集合中具有最低 Value 的节点
2. 需要能够高效地将节点插入到集合中
3. 两个节点可以有相同的值

我认为为此使用的最佳集合是某种排序列表。这样，只需从排序列表中取出第一个元素，就可以有效地满足要求#1。通过在列表中的正确位置插入新节点，可以有效地满足要求#2。

但是SortedList.Net 中的集合就像SortedDictionary并要求排序的键是唯一的，这违反了要求#3。

.Net 中似乎没有满足这些要求的集合，主要是因为确实存在的自排序集合要求排序的键是唯一的。这是什么原因呢？我认为这不可能是疏忽。我在这里没有抓住什么？我可以找到类似的问题，但它们通常涉及有人提出建议SortList，然后意识到这不起作用，然后对话就在没有标准解决方案的情况下消失了。至少如果有人会说“C# 中没有用于此任务的集合，您需要将一些东西组合在一起”，这将是一个答案。

每当添加新节点时使用常规List<Node>并重新排序列表是否可以接受？似乎这不如一开始就将节点插入到正确的位置那么有效。也许这就是我应该做的？手动迭代列表，直到找到自己插入新节点的位置？

Answer 1

如果您需要的只是有效插入并快速检索具有最低值的项目，那么您不需要排序列表。你需要一个堆。查看通用二进制堆类。