Search code examples
c#.netsortinggeneric-collections

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

Solution

  • 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/