c# - 维护一个排序列表

Question

我需要存储一组节点:

class Node
{
   int Value;
   //other info
}

我有三个要求:

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

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

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

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

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

Answer 1

如果您只需要高效地插入并快速检索具有最低值的项目，那么您不需要排序列表。你需要一个 heap .查看A Generic Binary Heap Class .