CODEWITHSUNDEEP
c#.netsortinggeneric-collections
OopsUser
OopsUser

Reputation: 4784

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

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 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 ?

Upvotes: 2

Views: 1582

Answers (3)

svick
svick

Reputation: 244837

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).

Upvotes: 3

Jim Mischel
Jim Mischel

Reputation: 134005

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.

Upvotes: 2

Nicholas Carey
Nicholas Carey

Reputation: 74277

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/

Upvotes: 4

Related Questions