Maintain a sorted list

Question

I need to save a collection of nodes:

class Node { int Value; //other info } 

I have three requirements:

• You must be able to efficiently retrieve the node with the lowest value in the collection
• You must be able to effectively insert node into the collection.
• Two nodes can have the same value.

I thought the best collection for this would be a sort of sorted list. Thus, requirement No. 1 is fulfilled efficiently by simply taking the first item from a sorted list. Requirement No. 2 is met efficiently by inserting a new node at the desired location in the list.

But .Net's SortedList collection is similar to SortedDictionary and requires the key to be sorted to be unique, which violates requirement # 3.

It seems that .Net does not have a collection that satisfies these requirements, mainly because existing self-distribution collections require keys to be sorted in order to be unique. What is the reason for this? I suppose this cannot be oversight. What I don’t understand here? I can find similar questions about this, but they usually include someone offering a SortList , after which awareness of this does not work, and then the conversation disappears without a standard solution. At least if someone said: "There is no collection in C # for this task, you need to hack something together," which would be the answer.

Is it possible to use a regular List<Node> and re-sort the list whenever a new node is added? It seems like this would not be as effective as inserting the node in the right place to start. Perhaps this is what I should do? Manually iterate over the list until I find a place to insert a new node myself?

Answer 1

If you only need to efficiently insert and quickly retrieve the element with the smallest value, you do not need a sorted list. You need a heap . Check out the General binary heap class .

Answer 2

Make your list unique by adding an object identifier or another unique identifier: identifiers 4 and 5, and both values ​​with a value of "1" will become "1_4" and "1_5", which can be added to the sorted list without problems and will be sorted, as was expected.

Answer 3

You can use SortedList<int, List<NodeInfo>> , where you put Value in the key and all other properties in the value:

 public class NodeList : SortedList<int, List<NodeInfo>> { public void Add(int key, NodeInfo info) { if (this.Keys.Contains(key)) { this[key].Add(info); } else { this.Add(key, new List<NodeInfo>() { info } ); } } public NodeInfo FirstNode() { if (this.Count == 0) return null; return this.First().Value.First(); } } public class NodeInfo { public string Info { get; set; } // TODO: add other members } 

Here is an example using the example:

 var list = new NodeList(); // adding list.Add(3, new NodeInfo() { Info = "some info 3" }); // inserting for (int i = 0; i < 100000; i++) { list.Add(1, new NodeInfo() { Info = "some info 1" }); list.Add(2, new NodeInfo() { Info = "some info 2" }); list.Add(1, new NodeInfo() { Info = "some info 1.1" }); } // retrieving the first item var firstNodeInfo = list.FirstNode(); // retrieving an item var someNodeInfo = list[2].First(); 

Answer 4

In my opinion, it is permissible to use a regular list and re-sort it after each insertion. Sorting is pretty efficient in .NET. See This Topic: Degree of degradation of row sorting in VS2010 and VS2008

Answer 5

You can use OrderedMultiDictionary in Wintellect Power Collections for .NET . This is exactly what you are looking for.