Which generic collection should i choose in C# to maintain sorted "list"

Question

I have Node class which has a float Distance property.

I want a data structure that i can put inside it all my nodes and they will be stored sorted (like in AVL tree or Red Black Tree).

• I want to insert in O(log(n))
• I want to retrieve and remove the minimum in O(log(n))

I tried to use sorted dictionary but it proved completely useless because he can't hold two items that have the same distance.

Using list and Sort i out of the question because removal is (O(n)) and finding Minimum is also (O(n))

All i need is a simple generic red black tree structure that will sort by some predicate i'll provide (which is to compare the Distance inside Node)

Is there such data structure in the BCL ?

Answer 1

You want to use the c5 Collections Library's TreeBag<T> class. It's a red-black tree that allows duplicates (hence, bag rather than set). access by index of item value is O(log n); insertion and deletion are O(log n) amortized.

The C5 Collection Library was funded by Microsoft; it's open-source and available gratis. The price is right.

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

Answer 2

Actually, you can use SortedDictionary for this. But what you need (assuming the distance is int) is a SortedDictionary<int, List<Item>>.

When you want to add a distance that's not in the dictionary yet, you insert a new List containing a single item. When you want to add a distance that is already in the dictionary, find the right list and add the item to it.

To remove the smallest item, find the List with the smallest key and remove an item from it. If the List becomes empty, remove it from the dictionary.

Since removing from the start of a List is inefficient, you will either need to remove from the end of the List (resulting in LIFO order for items with the same key), or use a Queue instead of List.

This is probably not the most efficient solution, but insertion, finding smallest item and removing smallest item are all O(log n).

Answer 3

Another option is a skip list. The .NET Framework doesn't have one, but I implemented one in C# a while back. See A More Memory-Efficient Skip List.

The skip list has O(log n) insertion, search, and removal, and O(1) removal of the top item.

If you want a heap, see A Generic Binary Heap Class.