C# Priority Queue Implementation for Silverlight

by filip 20. October 2008 19:23

While writing some code for Silverlight, I realized that Silverlight does not include a PriorityQueue implementation in their libraries.  I searched around, but I couldn't find any code that I thought was decent, so I wrote up something pretty quick.  I'll be testing this some more in the near future, but for now, I think it has the basics.  This should be fairly quick for large collections, as the enqueue is logarithmic, while the dequeue is pretty much as fast as it can be.

The queue uses generics for both the priority and the data that is being queued. The only thing to keep in mind is that if you're creating your own type for priority, it must implement IComparable.

 

   1: using System;
   2: using System.Collections.Generic; 
   3:  
   4: namespace bloodforge
   5: {
   6:     public class PriorityQueue<P, T>
   7:         where P : System.IComparable<P>
   8:     {
   9:         protected List<Queue<PriorityItem<P, T>>> _queues;
  10:         protected int _count; 
  11:  
  12:         public PriorityQueue()
  13:         {
  14:             _queues = new List<Queue<PriorityItem<P, T>>>();
  15:             _count = 0;
  16:         } 
  17:  
  18:         /// <summary>
  19:         /// Add an item to the priority queue
  20:         /// </summary>
  21:         public void Enqueue(P priority, T data)
  22:         {
  23:             if (_count == 0)
  24:             {
  25:                 Queue<PriorityItem<P, T>> NewQueue = new Queue<PriorityItem<P, T>>();
  26:                 NewQueue.Enqueue(new PriorityItem<P, T>(priority, data));
  27:                 _queues.Add(NewQueue);
  28:             }
  29:             else
  30:             {
  31:                 QueueInsert(priority, data, 0, _queues.Count - 1);
  32:             } 
  33:  
  34:             _count++;
  35:         } 
  36:  
  37:         /// <summary>
  38:         /// Helper method for Enqueue
  39:         /// </summary>
  40:         private void QueueInsert(P priority, T data, int qLo, int qHi)
  41:         {
  42:             if (qLo == qHi)
  43:             {
  44:                 // There is only one item left to compare.
  45:                 // Need to decide where this item belongs in relation to the last item.
  46:                 if (_queues[qLo].Peek().Priority.CompareTo(priority) < 0)
  47:                 {
  48:                     Queue<PriorityItem<P, T>> NewQueue = new Queue<PriorityItem<P, T>>();
  49:                     NewQueue.Enqueue(new PriorityItem<P, T>(priority, data));
  50:                     _queues.Insert(qLo, NewQueue);
  51:                     return;
  52:                 }
  53:                 else if (_queues[qLo].Peek().Priority.CompareTo(priority) > 0)
  54:                 {
  55:                     Queue<PriorityItem<P, T>> NewQueue = new Queue<PriorityItem<P, T>>();
  56:                     NewQueue.Enqueue(new PriorityItem<P, T>(priority, data));
  57:                     _queues.Insert(qLo + 1, NewQueue);
  58:                     return;
  59:                 }
  60:                 else
  61:                 {
  62:                     _queues[qLo].Enqueue(new PriorityItem<P, T>(priority, data));
  63:                     return;
  64:                 }
  65:             }
  66:             else
  67:             {
  68:                 // Get the middle item from the queue and see if we
  69:                 // need to go to the first or second half of the queues list
  70:                 int qMid = Convert.ToInt32(Math.Floor((qLo + qHi) / 2));
  71:                 if (_queues[qMid].Peek().Priority.CompareTo(priority) < 0)
  72:                 {
  73:                     // This item belongs in the upper half of the range
  74:                     QueueInsert(priority, data, qLo, qMid);
  75:                     return;
  76:                 }
  77:                 else if (_queues[qMid].Peek().Priority.CompareTo(priority) > 0)
  78:                 {
  79:                     // This item belongs in the lower half of the range
  80:                     QueueInsert(priority, data, qMid + 1, qHi);
  81:                     return;
  82:                 }
  83:                 else
  84:                 {
  85:                     // we got lucky, the middle item is of the same priority
  86:                     _queues[qMid].Enqueue(new PriorityItem<P, T>(priority, data));
  87:                     return;
  88:                 }
  89:             }
  90:         } 
  91:  
  92:         /// <summary>
  93:         /// Remove the top item from the queue
  94:         /// </summary>
  95:         public T Dequeue()
  96:         {
  97:             if (_queues.Count == 0)
  98:             {
  99:                 // There are no items in the priority queue
 100:                 return default(T);
 101:             } 
 102:  
 103:             // Get the first item from the first queue
 104:             T data = _queues[0].Dequeue().Data; 
 105:  
 106:             if (_queues[0].Count == 0)
 107:             {
 108:                 // If the queue at the top priority is empty, remove it
 109:                 _queues.RemoveAt(0);
 110:             } 
 111:  
 112:             _count--; 
 113:  
 114:             return data; 
 115:  
 116:         } 
 117:  
 118:         /// <summary>
 119:         /// Retrieves the top item from the queue without removing it
 120:         /// </summary>
 121:         public T Peek()
 122:         {
 123:             if (_queues.Count > 0)
 124:             {
 125:                   return _queues[0].Peek().Data;
 126:             }
 127:             else return default(T);
 128:         } 
 129:  
 130:         /// <summary>
 131:         /// Gets the number of items in the priority queue
 132:         /// </summary>
 133:         public int Count
 134:         {
 135:             get
 136:             {
 137:                 return _count;
 138:             }
 139:         } 
 140:  
 141:         /// <summary>
 142:         /// Returns a string representation of the queue
 143:         /// </summary>
 144:         public override string ToString()
 145:         {
 146:             string val = string.Empty;
 147:             foreach(Queue<PriorityItem<P, T>> queue in _queues)
 148:             {
 149:                 PriorityItem<P, T>[] items = queue.ToArray();
 150:                 foreach (PriorityItem<P, T> item in items)
 151:                 {
 152:                     val += string.Format(" [ {0} ] ", item.Data.ToString());
 153:                 }
 154:             }
 155:             return val.TrimEnd(',');
 156:         }
 157:     } 
 158:  
 159:     public class PriorityItem<P, T>
 160:         where P : System.IComparable<P>
 161:     {
 162:         public P Priority;
 163:         public T Data; 
 164:  
 165:         public PriorityItem(P priority, T data)
 166:         {
 167:             this.Priority = priority;
 168:             this.Data = data;
 169:         }
 170:     }
 171: } 

Tags: ,

Web Development

About Filip Stanek

Death Note Pic I'm a developer at ACG in Cincinnati, OH. I like ASP.NET, Flash, and other web technologies, & enjoy playing chess, video games, etc.

Currently playing:

Disqus

Month List