Maintaining a sorted list

Question

I need to store a collection of nodes:

class Node
{
   int Value;
   //other info
}

I have three requirements:

1. Need to be able to efficiently retrieve the node with the lowest Value in the collection
2. Need to be able to efficiently insert a node into the collection
3. Two nodes can have the same Value

I thought the best collection to use for this would be some sort of sorted list. That way requirement #1 is satisfied efficiently by just taking the first element from the sorted list. Requirement #2 is satisfied efficiently by inserting a new node in the right place in the list.

But the SortedList collection in .Net is like SortedDictionary and requires the key being sorted on to be unique, which violates requirement #3.

There appears to be no collection in .Net that satisfies these requirements, mainly because the self-sorting collections that do exist require keys being sorted on to be unique. What is the reason for this? I assume it cannot be an oversight. What am I not grasping here? I can find similar questions about this but they usually involve someone suggesting SortList, followed by realizing this doesn't work, and then the conversation fades out without a standard solution. At least if someone would say "There is no collection in C# for this task, you need to hack something together" that would be an answer.

Is it acceptable to use a regular List<Node> and re-sort the list whenever a new node is added? Seems like that wouldn't be as efficient as inserting the node in the right place to begin with. Perhaps that is what I should do? Manually iterate over the list until I find the place to insert a new node myself?

Answer 1

If all you need is to efficiently insert, and quickly retrieve the item with the lowest value, then you don't need a sorted list. You need a heap. Check out A Generic Binary Heap Class.

Answer 2

Make your list_key unique by adding the object id or another unique identifier: IDs 4 and 5, both having value "1" will become "1_4" and "1_5", which can be added to the sorted List without trouble and will be sorted as expected.

Answer 3

You could use a SortedList<int, List<NodeInfo>>, where you'll put the Value in the key and all the 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's some sample usage:

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 acceptable to use a normal list and re-sort it after every insert. Sorting is pretty efficient in .NET. See this thread : String sorting performance degradation in VS2010 vs. VS2008

Answer 5

You can use OrderedMultiDictionary in Wintellect's Power Collections for .NET. That's exactly what you are looking for.