Priority queue in Net

Question

I am looking for a  NET implementation of a priority queue or heap data structure     Priority queues are data structures that provide more flexibility than simple sorting  because they allow new elements to enter a system at arbitrary intervals  It is much more cost-effective to insert a new job into a priority queue than to re-sort everything on each such arrival       The basic priority queue supports three primary operations          Insert Q x   Given an item x with key k  insert it into the priority queue Q    Find-Minimum Q   Return a pointer to the item   whose key value is smaller than any other key in the priority queue   Q    Delete-Minimum Q   Remove the item from the priority queue Q whose key is minimum      Unless I am looking in the wrong place  there isn t one in the framework  Is anyone aware of a good one  or should I roll my own

User · Answer

You may find useful this implementation  http   www codeproject com Articles 126751 Priority-queue-in-Csharp-with-help-of-heap-data-st aspx  it is generic and based on heap data structure

User · Answer

The following implementation of a PriorityQueue uses SortedSet from the System library    using System  using System Collections Generic   namespace CDiggins       interface IPriorityQueue lt T  K gt  where K   IComparable lt K gt                bool Empty   get            void Enqueue T x  K key           void Dequeue            T Top   get               class PriorityQueue lt T  K gt    IPriorityQueue lt T  K gt  where K   IComparable lt K gt                SortedSet lt Tuple lt T  K gt  gt  set           class Comparer   IComparer lt Tuple lt T  K gt  gt                public int Compare Tuple lt T  K gt  x  Tuple lt T  K gt  y                    return x Item2 CompareTo y Item2                                    PriorityQueue     set   new SortedSet lt Tuple lt T  K gt  gt  new Comparer               public bool Empty   get   return set Count    0               public void Enqueue T x  K key    set Add Tuple Create x  key              public void Dequeue     set Remove set Max             public T Top   get   return set Max Item1

User · Answer

here s one i just wrote  maybe it s not as optimized  just uses a sorted dictionary  but simple to understand  you can insert objects of different kinds  so no generic queues   using System  using System Diagnostics  using System Collections  using System Collections Generic   namespace PrioQueue       public class PrioQueue               int total size          SortedDictionary lt int  Queue gt  storage           public PrioQueue                          this storage   new SortedDictionary lt int  Queue gt                  this total size   0                     public bool IsEmpty                          return  total size    0                      public object Dequeue                          if  IsEmpty                       throw new Exception   Please check that priorityQueue is not empty before dequeing                  else                 foreach  Queue q in storage Values                           we use a sorted dictionary                     if  q Count  gt  0                            total size--                          return q Dequeue                                                              Debug Assert false  not supposed to reach here  problem with changing total size                     return null     not supposed to reach here                        same as above  except for peek           public object Peek                          if  IsEmpty                     throw new Exception   Please check that priorityQueue is not empty before peeking                else                 foreach  Queue q in storage Values                        if  q Count  gt  0                          return q Peek                                        Debug Assert false  not supposed to reach here  problem with changing total size                     return null     not supposed to reach here                     public object Dequeue  int prio                        total size--              return storage prio  Dequeue                        public void Enqueue  object item  int prio                        if   storage ContainsKey  prio                     storage Add  prio  new Queue                                  storage prio  Enqueue  item               total size

User · Answer

A Simple Max Heap Implementation   https   github com bharathkumarms AlgorithmsMadeEasy blob master AlgorithmsMadeEasy MaxHeap cs  using System  using System Collections Generic  using System Linq   namespace AlgorithmsMadeEasy       class MaxHeap               private static int capacity   10          private int size   0          int   items   new int capacity            private int getLeftChildIndex int parentIndex    return 2   parentIndex   1            private int getRightChildIndex int parentIndex    return 2   parentIndex   2            private int getParentIndex int childIndex    return  childIndex - 1    2             private int getLeftChild int parentIndex    return this items getLeftChildIndex parentIndex              private int getRightChild int parentIndex    return this items getRightChildIndex parentIndex              private int getParent int childIndex    return this items getParentIndex childIndex               private bool hasLeftChild int parentIndex    return getLeftChildIndex parentIndex   lt  size            private bool hasRightChild int parentIndex    return getRightChildIndex parentIndex   lt  size            private bool hasParent int childIndex    return getLeftChildIndex childIndex   gt  0             private void swap int indexOne  int indexTwo                        int temp   this items indexOne               this items indexOne    this items indexTwo               this items indexTwo    temp                     private void hasEnoughCapacity                         if  this size    capacity                                Array Resize ref this items capacity 2                   capacity    2                                   public void Add int item                        this hasEnoughCapacity                this items size    item              this size                heapifyUp                       public int Remove                         int item   this items 0               this items 0    this items size-1               this items this size - 1    0              size--              heapifyDown                return item                     private void heapifyUp                         int index   this size - 1              while  hasParent index   amp  amp  this items index   gt  getParent index                                 swap index  getParentIndex index                    index   getParentIndex index                                    private void heapifyDown                         int index   0              while  hasLeftChild index                                 int bigChildIndex   getLeftChildIndex index                   if  hasRightChild index   amp  amp  getLeftChild index   lt  getRightChild index                                         bigChildIndex   getRightChildIndex index                                      if  this items bigChildIndex   lt  this items index                                         break                                    else                                       swap bigChildIndex index                       index   bigChildIndex                                                        Calling Code      MaxHeap mh   new MaxHeap        mh Add 10       mh Add 5       mh Add 2       mh Add 1       mh Add 50       int maxVal    mh Remove        int newMaxVal   mh Remove

User · Answer

I had the same issue recently and ended up creating a NuGet package for this   This implements a standard heap-based priority queue  It also has all the usual niceties of the BCL collections  ICollection lt T gt  and IReadOnlyCollection lt T gt  implementation  custom IComparer lt T gt  support  ability to specify an initial capacity  and a DebuggerTypeProxy to make the collection easier to work with in the debugger   There is also an Inline version of the package which just installs a single  cs file into your project  useful if you want to avoid taking externally-visible dependencies    More information is available on the github page

User · Answer

I found one by Julian Bucknall on his blog here - http   www boyet com Articles PriorityQueueCSharp3 html  We modified it slightly so that low-priority items on the queue would eventually  bubble-up  to the top over time  so they wouldn t suffer starvation

User · Answer

I like using the OrderedBag and OrderedSet classes in PowerCollections as priority queues

User · Answer

AlgoKit  I wrote an open source library called AlgoKit  available via NuGet  It contains    Implicit d-ary heaps  ArrayHeap   Binomial heaps  Pairing heaps    The code has been extensively tested  I definitely recommend you to give it a try   Example  var comparer   Comparer lt int gt  Default  var heap   new PairingHeap lt int  string gt  comparer    heap Add 3   your    heap Add 5   of    heap Add 7   disturbing     heap Add 2   find    heap Add 1   I    heap Add 6   faith    heap Add 4   lack     while   heap IsEmpty      Console WriteLine heap Pop   Value     Why those three heaps   The optimal choice of implementation is strongly input-dependent     as Larkin  Sen  and Tarjan show in A back-to-basics empirical study of priority queues  arXiv 1403 0252v1  cs DS   They tested implicit d-ary heaps  pairing heaps  Fibonacci heaps  binomial heaps  explicit d-ary heaps  rank-pairing heaps  quake heaps  violation heaps  rank-relaxed weak heaps  and strict Fibonacci heaps   AlgoKit features three types of heaps that appeared to be most efficient among those tested   Hint on choice  For a relatively small number of elements  you would likely be interested in using implicit heaps  especially quaternary heaps  implicit 4-ary   In case of operating on larger heap sizes  amortized structures like binomial heaps and pairing heaps should perform better

User · Answer

You might like IntervalHeap from the C5 Generic Collection Library  To quote the user guide  Class IntervalHeap lt T gt  implements interface IPriorityQueue lt T gt  using an interval heap stored as an array of pairs  The FindMin and FindMax operations  and the indexer   s get-accessor  take time O 1   The DeleteMin  DeleteMax  Add and Update operations  and the indexer   s set-accessor  take time O log n   In contrast to an ordinary priority queue  an interval heap offers both minimum and maximum operations with the same efficiency   The API is simple enough  gt  var heap   new C5 IntervalHeap lt int gt      gt  heap Add 10    gt  heap Add 5    gt  heap FindMin    5  Install from Nuget https   www nuget org packages C5 or GitHub  https   github com sestoft C5

User · Answer

Here s my attempt at a  NET heap  public abstract class Heap lt T gt    IEnumerable lt T gt        private const int InitialCapacity   0      private const int GrowFactor   2      private const int MinGrow   1       private int  capacity   InitialCapacity      private T    heap   new T InitialCapacity       private int  tail   0       public int Count   get   return  tail          public int Capacity   get   return  capacity           protected Comparer lt T gt  Comparer   get  private set        protected abstract bool Dominates T x  T y        protected Heap     this Comparer lt T gt  Default                   protected Heap Comparer lt T gt  comparer    this Enumerable Empty lt T gt     comparer                   protected Heap IEnumerable lt T gt  collection            this collection  Comparer lt T gt  Default                   protected Heap IEnumerable lt T gt  collection  Comparer lt T gt  comparer                if  collection    null  throw new ArgumentNullException  collection            if  comparer    null  throw new ArgumentNullException  comparer             Comparer   comparer           foreach  var item in collection                        if  Count    Capacity                  Grow                  heap  tail      item                     for  int i   Parent  tail - 1   i  gt   0  i--              BubbleDown i              public void Add T item                if  Count    Capacity              Grow              heap  tail      item          BubbleUp  tail - 1              private void BubbleUp int i                if  i    0    Dominates  heap Parent i     heap i                 return    correct domination  or root           Swap i  Parent i            BubbleUp Parent i               public T GetMin                 if  Count    0  throw new InvalidOperationException  Heap is empty            return  heap 0              public T ExtractDominating                 if  Count    0  throw new InvalidOperationException  Heap is empty            T ret    heap 0            tail--          Swap  tail  0           BubbleDown 0           return ret             private void BubbleDown int i                int dominatingNode   Dominating i           if  dominatingNode    i  return          Swap i  dominatingNode           BubbleDown dominatingNode              private int Dominating int i                int dominatingNode   i          dominatingNode   GetDominating YoungChild i   dominatingNode           dominatingNode   GetDominating OldChild i   dominatingNode            return dominatingNode             private int GetDominating int newNode  int dominatingNode                if  newNode  lt   tail  amp  amp   Dominates  heap dominatingNode    heap newNode                return newNode          else             return dominatingNode             private void Swap int i  int j                T tmp    heap i            heap i     heap j            heap j    tmp             private static int Parent int i                return  i   1  2 - 1             private static int YoungChild int i                return  i   1  2 - 1             private static int OldChild int i                return YoungChild i    1             private void Grow                 int newCapacity    capacity GrowFactor   MinGrow          var newHeap   new T newCapacity           Array Copy  heap  newHeap   capacity            heap   newHeap           capacity   newCapacity             public IEnumerator lt T gt  GetEnumerator                 return  heap Take Count  GetEnumerator               IEnumerator IEnumerable GetEnumerator                 return GetEnumerator             public class MaxHeap lt T gt    Heap lt T gt        public MaxHeap             this Comparer lt T gt  Default                   public MaxHeap Comparer lt T gt  comparer            base comparer                   public MaxHeap IEnumerable lt T gt  collection  Comparer lt T gt  comparer            base collection  comparer                   public MaxHeap IEnumerable lt T gt  collection    base collection                   protected override bool Dominates T x  T y                return Comparer Compare x  y   gt   0           public class MinHeap lt T gt    Heap lt T gt        public MinHeap             this Comparer lt T gt  Default                   public MinHeap Comparer lt T gt  comparer            base comparer                   public MinHeap IEnumerable lt T gt  collection    base collection                   public MinHeap IEnumerable lt T gt  collection  Comparer lt T gt  comparer            base collection  comparer                   protected override bool Dominates T x  T y                return Comparer Compare x  y   lt   0            Some tests    TestClass  public class HeapTests        TestMethod      public void TestHeapBySorting                 var minHeap   new MinHeap lt int gt  new    9  8  4  1  6  2  7  4  1  2            AssertHeapSort minHeap  minHeap OrderBy i   gt  i  ToArray              minHeap   new MinHeap lt int gt    7  5  1  6  3  2  4  1  2  1  3  4  7            AssertHeapSort minHeap  minHeap OrderBy i   gt  i  ToArray              var maxHeap   new MaxHeap lt int gt  new    1  5  3  2  7  56  3  1  23  5  2  1            AssertHeapSort maxHeap  maxHeap OrderBy d   gt  -d  ToArray              maxHeap   new MaxHeap lt int gt   2  6  1  3  56  1  4  7  8  23  4  5  7  34  1  4           AssertHeapSort maxHeap  maxHeap OrderBy d   gt  -d  ToArray                private static void AssertHeapSort Heap lt int gt  heap  IEnumerable lt int gt  expected                var sorted   new List lt int gt             while  heap Count  gt  0              sorted Add heap ExtractDominating              Assert IsTrue sorted SequenceEqual expected

User · Answer

As mentioned in Microsoft Collections for  NET  Microsoft has written  and shared online  2 internal PriorityQueue classes within the  NET Framework  Their code is available to try out  As  mathusum-mut commented  there is a bug in one of Microsoft s internal PriorityQueue classes  the SO community has  of course  provided fixes for it   Bug in Microsoft  39 s internal PriorityQueue lt T gt

User · Answer

I found one by Julian Bucknall on his blog here - http   www boyet com Articles PriorityQueueCSharp3 html  We modified it slightly so that low-priority items on the queue would eventually  bubble-up  to the top over time  so they wouldn t suffer starvation

User · Answer

class PriorityQueue lt T gt        IComparer lt T gt  comparer      T   heap      public int Count   get  private set        public PriorityQueue     this null          public PriorityQueue int capacity    this capacity  null          public PriorityQueue IComparer lt T gt  comparer    this 16  comparer          public PriorityQueue int capacity  IComparer lt T gt  comparer                this comparer    comparer    null    Comparer lt T gt  Default   comparer          this heap   new T capacity             public void push T v                if  Count  gt   heap Length  Array Resize ref heap  Count   2           heap Count    v          SiftUp Count               public T pop                 var v   top            heap 0    heap --Count           if  Count  gt  0  SiftDown 0           return v            public T top                 if  Count  gt  0  return heap 0           throw new InvalidOperationException                      void SiftUp int n                var v   heap n           for  var n2   n   2  n  gt  0  amp  amp  comparer Compare v  heap n2    gt  0  n   n2  n2    2  heap n    heap n2           heap n    v            void SiftDown int n                var v   heap n           for  var n2   n   2  n2  lt  Count  n   n2  n2    2                        if  n2   1  lt  Count  amp  amp  comparer Compare heap n2   1   heap n2    gt  0  n2                if  comparer Compare v  heap n2    gt   0  break              heap n    heap n2                     heap n    v            easy

User · Answer

Use a Java to C  translator on the Java implementation  java util PriorityQueue  in the Java Collections framework  or more intelligently use the algorithm and core code and plug it into a C  class of your own making that adheres to the C  Collections framework API for Queues  or at least Collections

User · Answer

Here is the another implementation from NGenerics team   NGenerics PriorityQueue

[c#] Priority queue in .Net

Examples related to c#

Examples related to .net

Examples related to data-structures

Examples related to heap

Examples related to priority-queue