Skip to content
Concurrent priority queue and skip list for .NET
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
DataStructures
Tests
.gitattributes
.gitignore
DataStructures.sln
License.md
README.md

README.md

C# implementations of some usefull data sctructures for .NET

##Priority queue Heap-based generic concurrent priority queue for .NET

Priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

###Features

  • Generic
  • Thread-safe using ReaderWriterLockSlim
  • Performant
    • Take max item, Insertion, Removal - O(N log N)
  • Resizable (queue grows and shrinks depending on the number of items)

#NuGet

###Applications

##Skip list Generic concurrent skiplist for .NET

This data structure makes random choices in arranging the entries in such a way that search and update times are O(log N) on average, where N is the number of entries in the list. Interestingly, the notion of average time complexity used here does not depend on the probability distribution of the keys in the input. Instead, it depends on the use of a random-number generator in the implementation of the insertions to help decide where to place the new entry. [Detailed overview] (https://msdn.microsoft.com/en-us/library/ms379573(VS.80).aspx#datastructures20_4_topic4) of skip list and a simple implementation.

###Features

  • Generic
  • Thread-safe using ReaderWriterLockSlim
  • Performant
    • Take min or max item - O(1)
    • Insertion, Removal, Check if contains - O(log N)
    • Enumeration in order - O(N)
  • Additional operations
    • Get Floor and Clealing items - O(log N)
    • Get items in range O(log N + K) (where K is number of items in result)

###Applications

#License Released under the MIT license.

You can’t perform that action at this time.